require 'lib2'

# 長さ2の配列の整列
def sort2(a)     # 逆順ならば昇順に並べ変える
  if a[0] > a[1]; swap(a, 0, 1); end
end

# 長さ3の配列の整列
def sort3(a)
  if a[1] <= a[0]; swap(a, 0, 1); end
  if a[2] <= a[0]; swap(a, 0, 2); end
  if a[2] <= a[1]; swap(a, 1, 2); end
end

# 選択整列
def selection_sort(a)
  n = a.length
  for i in 0 ... n do     
    min = min_index(a, i, n)
    swap(a, i, min)
  end
end

# 挿入整列
def insertion_sort(a)
  n = a.length
  for i in 0 ... n do
    insert_element(a, i, a[i])
  end
end

# クイックソート
def quick_sort(a)
  n = a.length
  qsort(a, 0, n-1)
end

# クイックソートの本体
def qsort(a, left, right)
  if left < right
    v = a[right]   # この要素を left〜right の間の正しい位置へ移動
    i = left-1
    j = right
    while true
      # このループ内の条件は微妙なため単純に < を <= に
      # 変更したりすると動作が正しくなくなるので注意
      i+=1; while a[i] < v do; i+=1; end
      j-=1; while a[j] > v do; j-=1; end
      if i >= j; break; end  # while ループを終了
      swap(a, i, j)
    end
    swap(a, i, right)
    # この時点で a[i] を軸として分割終了
    qsort(a, left, i-1)
    qsort(a, i+1, right)
  end
end