クイックソート
つなぐときに、また比べ直している
マージソートは真ん中でまっぷたつに割ります。割った時点では、どちらの側にどんな値が入ったか分かりません。だから最後につなぐときに、あらためて全部を見比べる必要がありました。
では、割る前に基準を決めておけばどうでしょう。「この値より小さいものは左の箱、大きいものは右の箱」と振り分けてしまえば、左の箱の中身は右の箱のどれよりも小さいと確定します。つなぐときに比較は 1 回も要りません。
基準を 1 つ選んで、3 つの箱に配る
[6, 3, 8, 5, 2, 7, 1, 4] の真ん中の値 5 を基準にします。先頭から 1 つずつ見て、箱に入れていきます。
- 5 より小さい箱 —
3, 2, 1, 4 - 5 と等しい箱 —
5 - 5 より大きい箱 —
6, 8, 7
同じやり方で左の箱を並べると [1, 2, 3, 4]、右の箱は [6, 7, 8] になります。あとは順につなぐだけで [1, 2, 3, 4, 5, 6, 7, 8] です。基準の 5 は、配った時点ですでに最終的な位置が決まっていました。
等しい値の箱を別に作るのがコツです。基準そのものを小さい箱にも大きい箱にも入れないので、配るたびに要素が必ず 1 つ以上減ります。[3, 3, 3, 3] のように全部同じ値でも、1 回配れば等しい箱に全部入って終わります。
基準の選び方で速さが決まる
配るたびに中身が半分ずつになれば、段の数は要素数を 2 で割り続けられる回数で済みます。問題は、半分にならない選び方をしたときです。
Python
nums = [1, 2, 3, 4, 5]
pivot = nums[0] # 先頭を基準にすると
# 小さい箱は空、大きい箱は [2, 3, 4, 5]1 個しか減っていません。これを繰り返すと段が要素数ぶん積み上がり、手間は 2 乗に戻ります。しかも、こうなるのは並べ替える必要がいちばん薄い「すでに並んだ入力」のときです。真ん中を取る、乱数で選ぶ、先頭と真ん中と末尾の 3 つの中央値を取る、といった選び方はこれを避けるための工夫です。
ここまでの 5 つを並べておきます。
| 並べ替え | 平均 | 最悪 | 追加のメモリ |
|---|---|---|---|
| バブル | O(n^2) | O(n^2) | ほぼ不要 |
| 選択 | O(n^2) | O(n^2) | ほぼ不要 |
| 挿入 | O(n^2) / ほぼ並んだ入力は O(n) | O(n^2) | ほぼ不要 |
| マージ | O(n log n) | O(n log n) | 入力と同じだけ |
| クイック | O(n log n) | O(n^2) | 基準の選び方しだい |
よくある間違い
基準の値をどの箱にも入れ忘れることです。小さい箱と大きい箱の 2 つだけで振り分けると、基準そのものが結果から消えます。逆に、基準を大きい箱のほうにも残してしまうと要素が減らず、同じ配列をいつまでも配り続けます。
要件
- 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
- ピボットを選んで less / equal / greater に分割し、再帰的にソートする
- 戻り値は新しい配列で、入力 arr を破壊的に書き換えない
入出力例
quickSort([6,3,8,5,2,7,1,4]) → [1,2,3,4,5,6,7,8]
quickSort([1,2,3,4]) → [1,2,3,4]
quickSort([4,3,2,1]) → [1,2,3,4]
quickSort([3,3,3,3]) → [3,3,3,3]
quickSort([100]) → [100]
quickSort([2,1,2,3,1]) → [1,1,2,2,3]
quickSort([-1,4,-3,0,2,-5]) → [-5,-3,-1,0,2,4]ヒント
