# 2006-01-30 by nagoya

# 配列 a の i 番目の要素と j 番目の要素を交換する。
def swap(a, i, j)
  t = a[i]
  a[i] = a[j]
  a[j] = t
end

# 配列 a における i 番目から j-1 番目
# の範囲で最小の要素の添字を返す。
# ただし i <= j と仮定。
def min_index(a, i, j)
  min = i
  for k in i+1 ... j do
    if a[k] < a[min]
      min = k
    end
  end
  return min
end

# a[0] から a[i-1] まですでに整列済みの
# 配列 a を、新しい要素 v を含めて a[0]
# から a[i] まで整列済みとする。
def insert_element(a, i, v)
  j = i-1
  while j >= 0 and a[j] > v
     a[j+1] = a[j]
     j -= 1                 
  end
  a[j+1] = v
end