クイックソートとは？
クイックソート(Quick Sort)は、基準値(ピボット, pivot)を1つ決め、それより小さい値を左・大きい値を右に分けたあと、両側を同じ方法で再び整列する分割統治(divide and conquer)アルゴリズムです。マージソートと並んで平均O(n log n)を代表しますが、追加メモリをほとんど使わずその場(in-place)で整列する点が異なります。
核心の一行: 「ピボットを定位置に置く」。 一度の分割が終わると、ピボットは整列完了時の最終位置にぴったり収まります。
核心は分割(partition)
クイックソートのほぼ全ての仕事は分割ステップで起こります。
1. 区間の1要素をピボットに選ぶ(ここでは最後の値)。
2. 区間を走査し、ピボットより小さい値を前方に集める。
3. 最後にピボットをその境界へ移すと、ピボットの左は全て小さく、右は全て大きい状態になる。
これでピボットは触れる必要がありません。左区間と右区間をそれぞれ独立に同じ分割で繰り返せば、全体が整列します。
動作原理
ステップ1. 整列する区間 [lo, hi] で pivot = arr[hi] とします。
ステップ2. 境界インデックス i = lo を置きます。j を lo から hi-1 まで動かし、arr[j] < pivot なら arr[i] と交換して i を1増やします。
ステップ3. 走査が終わったら arr[i] と arr[hi](ピボット)を交換します。これでピボットはインデックス i に確定します。
ステップ4. [lo, i-1] と [i+1, hi] についてステップ1〜3を再帰で繰り返します。区間サイズが1以下なら止めます。
「比較」と「交換」は別々の動作です。AlgoNoteの可視化も比較ステップと交換ステップを分けて示します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間(平均) | O(n log n) |
| 時間(最悪) | O(n²) |
| 空間 | O(log n) |
平均的には分割が半分ずつ起こり深さがlog n、各深さでn回比較するのでO(n log n)です。しかし既に整列された配列で常に末尾をピボットにすると片側が空になり深さがnまで伸びてO(n²)になります。空間は再帰スタック分(O(log n))で、大きな補助配列は使いません。
例で追ってみる
arr = [5, 2, 8, 1, 4] で末尾の値 4 をピボットにします。
- •j=0: 5 < 4? いいえ
- •j=1: 2 < 4? はい → arr[0]と交換 →
[2, 5, 8, 1, 4]、i=1 - •j=2: 8 < 4? いいえ
- •j=3: 1 < 4? はい → arr[1]と交換 →
[2, 1, 8, 5, 4]、i=2 - •最後にarr[2]とピボットを交換 →
[2, 1, 4, 5, 8]
ピボット 4 はインデックス2に確定し、左 [2, 1] と右 [5, 8] を再び整列すれば完了です。
よくあるミス
- •ピボット選択: 常に末尾を選ぶと整列済み入力でO(n²)。ランダムピボットやmedian-of-threeで緩和します。
- •不等号の扱い:
arr[j] < pivotの不等号を誤ると重複値が多いとき分割が片側に偏り性能が落ちます。 - •終了条件:
lo < hiのときだけ分割し、要素1個以下の区間は既に整列済みです。
AlgoNoteで直接確認しましょう
ピボットがどう決まり、小さい値が前に集まり、ピボットが定位置を見つける過程をAlgoNoteでステップごとに確認できます。