クイックソート

『基礎から学ぶデータ構造とアルゴリズム』「4.4 クイックソート」の勉強メモです。自分なりに咀嚼したソート手順とサンプルコード（Ruby）をまとめています。

1. データ列の任意の要素を枢軸値（pivot）に選ぶ
2. データ列を枢軸値よりも小さな値のデータ列と大きな値のデータ列に分ける。これを再帰的に行う

def quick_sort(a, l, r)
  return if l >= r

  i = l
  j = r
  pivot = a[(i + j) / 2]
  while true
    i += 1 while a[i] < pivot
    j -= 1 while a[j] > pivot
    break if i >= j
    a[i], a[j] = a[j], a[i]
    p a
    i += 1
    j -= 1
  end

  quick_sort a, l, i - 1
  quick_sort a, j + 1, r
end

a = [10, 25, 75, 5, 30, 35, 15, 90, 65, 80, 50, 45]
quick_sort a, 0, a.size - 1

[10, 25, 15, 5, 30, 35, 75, 90, 65, 80, 50, 45]
[10, 5, 15, 25, 30, 35, 75, 90, 65, 80, 50, 45]
[5, 10, 15, 25, 30, 35, 75, 90, 65, 80, 50, 45]
[5, 10, 15, 25, 30, 35, 45, 90, 65, 80, 50, 75]
[5, 10, 15, 25, 30, 35, 45, 50, 65, 80, 90, 75]
[5, 10, 15, 25, 30, 35, 45, 50, 65, 80, 75, 90]
[5, 10, 15, 25, 30, 35, 45, 50, 65, 75, 80, 90]

リンク

• バブルソート、選択ソート、挿入ソート
• シェルソート
• マージソート