(1) クイックソート

クイックソートとは

クイックソートは、最も速くソートできるアルゴリズムなのです。ある基準（ピボットpivot）によって値を２つのグループに分割し、それぞれのグループに対して同じ処理を繰り返します。

手順

  1. 開始位置(start)が終了位置(end)以上の場合、終了します。
  2. 開始位置(start)と終了位置(end)の中央値をpivotに設定します。
  3. 変数leftに開始位置(start)，rightに終了位置(end)を代入します。left，rightは調べる値のインデックス番号です。
  4. left≦rightのあいだ次の操作を繰り返します。
    1. pivotより左側で、pivotより大きい値を左端から順に探します（左側の交換対象の値）。
    2. pivotより右側で、pivotより小さい値を右端から順に探します（右側の交換対象の値）。
    3. leftがright以下の場合、左側と右側の交換対象の値を交換し、次の交換対象の値を探します。
  5. (4)のループが終了すると、配列はpivotを中心に分割されます。
    1. 分割された左側の配列に対して、同様に(1)〜(5)を行います。
    2. 分割された右側の配列に対して、同様に(1)〜(5)を行います。

実際のプログラムでは、pivotの決め方はいろいろな方法が使われています。上記のように、中央の値にする場合もありますが、そもそもソートされていないので中央の値が昇順における中央値であるとは限りません。そこで、例えば、ランダムに選んだ値をpivotにしたり、ランダムに選んだ複数の値の平均値や中央値をpivotにすることもあります。

デモンストレーション

pivot

プログラム（位置交換）

Colaboratoryのノートブックに書き写しながら、理解しましょう。

#クイックソート def quick_sort(arr, start, end): if start >= end: # startがend以上の場合、処理を終了 return middle = (start + end) // 2 # 中央の位置を求める pivot = arr[middle] # pivotを求める left = start # 左側の比較対象のインデックス番号 right = end # 右側の比較対象のインデックス番号 while left <= right: # leftがright以下のあいだ繰り返す（leftがrightより大きくなったら繰り返しを止める） while arr[left] < pivot: # 左側の値がpivotより小さければ、１つ右の値を対象にする left = left + 1 while arr[right] > pivot: # 右側の値がpivotより大きければ、１つ左の値を対象にする right = right - 1 if left <= right: # leftがright以下の場合、要素を交換し、leftとrightを次に進める tmp = arr[left] arr[left] = arr[right] arr[right] = tmp left = left + 1 right = right - 1 # ここまでで、pivotよりも左側に小さい値、右側に大きい値が移動している # 再帰的にクイックソートを左側の配列と右側の配列で実行 quick_sort(arr, start, right) # 左側の配列についてクイックソートを実行 quick_sort(arr, left, end) # 右側の配列についてクイックソートを実行 arr = [6, 3, 2, 0, 7, 1, 4, 5] print(arr) # 元の配列の表示 quick_sort(arr, 0, len(arr) - 1) # クイックソート関数を呼び出し print(arr) # ソート後の配列の表示
[6, 3, 2, 0, 7, 1, 4, 5] [0, 1, 2, 3, 4, 5, 6, 7]

プログラム（Pythonらしい書き方）

関数型プログラミング言語であるPythonらしい書き方をすると、次のようになります。上記では既存の配列内の要素の位置を交換していましたが、次の例では、新しい配列をつくって結果として返すようにしています。

#クイックソート def quick_sort(arr): # ソートすべき要素が1つ以下の場合、そのまま返す if len(arr) <= 1: return arr # ピボットとして中央の要素を選択 pivot = arr[len(arr) // 2] left = [] middle = [] right = [] # arrの要素を、ピボットより小さいか、等しいか、大きいかに基づいて、 # left, middle, rightのリストに分ける for x in arr: if x < pivot: left.append(x) elif x == pivot: middle.append(x) else: right.append(x) # leftとrightのリストを再帰的にソートし、結果を連結して返す return quick_sort(left) + middle + quick_sort(right) arr = [6, 3, 2, 0, 7, 1, 4, 5] #元のリスト print(arr) #ソート前を出力 arr = quick_sort(arr) # クイックソートを実行 print(arr) #ソート後
[6, 3, 2, 0, 7, 1, 4, 5] [0, 1, 2, 3, 4, 5, 6, 7]

さらに内包表記を用いると、次のように簡潔に書くことができます。

#クイックソート def quick_sort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quick_sort(left) + middle + quick_sort(right) arr = [6, 3, 2, 0, 7, 1, 4, 5]#元のリスト print(arr) #ソート前 arr = quick_sort(arr) print(arr) #ソート後
[6, 3, 2, 0, 7, 1, 4, 5] [0, 1, 2, 3, 4, 5, 6, 7]

このアルゴリズムの特徴

このサイトで紹介した他のソートの交換回数は、\(n^2\) に比例しているのに対して、クイックソートでは基準値を元に２分割しながらソートをしていくので、バイナリサーチ（二分探索）と同じようにデータ数が大きくなっても処理回数が膨大になりにくいという特徴があります。

しかしながら、逆順に並べられている場合など、特定の条件においては比較回数を行う回数が膨大になり、選択ソートや挿入ソートよりも処理に必要な時間が多くなることもありますので、必ずしも常にクイックソートの方が優れているというわけではありません（ほぼソートされている配列に対しては、挿入ソートの方が速いです）。

交換回数

クイックソートの交換回数が最小となる場合は、データをちょうど半分ずつに分割していくときです。\(n\) 個のデータを\(x\) 回分割すると、分割後のデータは\(n/2^x\) 個となります。分割後のデータの個数が1になったときにソートが完了しますので、

\[ 1 = \frac{n}{2^x} \]

と表せます。よって、分割回数\(x\) は、

\[ x = \log_2{n} \]

となります。1回の分割に必要な比較回数は\(n\) 回なので、

\[ 最小比較回数 = n\log_2{n} \]

となります。

一方、交換回数が最大となる場合は、すべての分割において、データが1個と残りすべてに分割されるときです。1回目で\(n\) 個のデータを1個と\(n-1\) 個，2回目で\(n-1\) 個のデータを1個と\(n-2\) 個，3回目で\(n-2\) 個のデータを1個と\(n-3\) 個，・・・，\(n-1\) 回目で2個のデータを1個ずつに分割してソートが完了します。つまり、比較回数は、1回目で\(n-1\) 回，2回目で\(n-2\) 回，3回目で\(n-3\) 回，・・・，\(n-1\)回目で1回となるので、

\[ 最大比較回数 = (n-1) + (n-2) + \cdots + 1 = \frac{1}{2} n (n-1) \]

となります。

最大比較回数は他のソートのアルゴリズムと同じくらいですが、このような場合は非常に稀なケースです。ほとんどの場合は、最小比較回数よりも数回多いくらいで完了しますので、他のソートのアルゴリズムよりも高速とされています（平均比較回数を求めるのは非常に困難なので、ここでは省略します）。