女性向けエンジニアスクール
3秒でわかる
基準値より小さい組と大きい組に分けることを繰り返して並べ替える手法。平均的に最も速い部類で、多くの言語の標準ソートの土台になっています。
もう少し詳しく
どういうものか
クイックソートは、配列から基準値 (ピボット) を 1 つ選び、それより小さい要素を左へ、大きい要素を右へ振り分け、左右それぞれに同じことを繰り返す並べ替えの手法です。分けた時点でピボットの位置は確定するので、振り分けが終われば全体が並びます。
平均の計算量は O(n log n) です。分割のたびに対象が半分ずつになるので、要素が 100 万件でも段数は 20 段ほどにしかなりません。
なぜ必要か
同じ O(n log n) のマージソートと比べたとき、クイックソートは追加の配列をほとんど使わずに済みます。配列の中で要素を交換していくだけなので、メモリの使用量が少なく、連続した領域を順に触るためキャッシュにも乗りやすいという実測上の強みがあります。実務で自分で書く場面は少ないものの、標準ライブラリの中身がこれなので、なぜ速いのかを説明できることが求められます。
具体例
def quick_sort(items):
if len(items) <= 1:
return items
pivot = items[len(items) // 2]
smaller = [x for x in items if x < pivot]
equal = [x for x in items if x == pivot]
larger = [x for x in items if x > pivot]
return quick_sort(smaller) + equal + quick_sort(larger)
print(quick_sort([5, 3, 8, 1, 9, 2, 7]))
# [1, 2, 3, 5, 7, 8, 9]分かりやすさのために新しいリストを作っていますが、本来は配列内の交換だけで行います。
つまずきやすいところ
ピボットに常に先頭要素を選ぶ実装は、すでに並んでいる配列を渡されたときに最悪の O(n^2) まで落ちます。分割が「1 個と残り全部」になり、段数が n 段になるためです。中央の要素を選ぶ、3 つの中央値を取る、乱数で選ぶといった工夫で避けます。
もう 1 つは、ピボットと等しい値の扱いです。等しい要素を左右どちらにも入れない実装にしないと、同じ値ばかりの配列で無限に再帰します。
似た用語との違い
| 手法 | 平均 | 最悪 | 安定性 |
|---|---|---|---|
| クイックソート | O(n log n) | O(n^2) | 安定でない |
| マージソート | O(n log n) | O(n log n) | 安定 |
| バブルソート | O(n^2) | O(n^2) | 安定 |
安定とは、同じ値の要素の元の並び順が保たれることです。
覚え方
「まず基準を決めて 2 つの山に分ける」。分けた瞬間に基準の場所が決まる、が要点です。
