クイックソート
クイックソート
このレッスンで分かること
- 「ピボットを基準に小・等・大に分ける」 — クイックソートの心臓部はこれだけ
クイックソート (quick sort)は、実用ソートの代表格です- アルゴリズムの中心は ピボット選択と分割 です
クイックソート とは
ピボットを基準に左右に分けて再帰的にソートするクイックソートを実装する。本レッスンでは、クイックソート の基本から実際の使いどころまでを整理し、現場で迷わず使える形に落とし込みます。
クイックソート (quick sort) は、実用ソートの代表格です。平均計算量 O(n log n) で マージソートよりも定数倍が小さく、in-place実装ではメモリを追加でほぼ必要としないため、多くのライブラリ実装の中核に使われています (なお本レッスンのコードは分かりやすさ優先でリスト内包表記を使うため O(n) の追加メモリを消費します) (例えば C++ の std::sort の一部、Java の Arrays.sort(int[]) のベース)。
アルゴリズムの中心は ピボット選択と分割 です。配列の中から 1 つ pivot を選び、「pivot 未満を左に、pivot を超える値を右に」並べ替えてから、左右をそれぞれ再帰的にクイックソートします。
クイックソートは平均
O(n log n)だが、最悪はO(n^2)。ピボット選択が下手だと劣化する。
アルゴリズムの動き
[6, 3, 8, 5, 2, 7, 1, 4] を最後の要素 4 をピボットにしてソートします。
- 分割後:
less = [3, 2, 1],equal = [4],greater = [6, 8, 5, 7] lessを再帰:[1, 2, 3]greaterを再帰:[5, 6, 7, 8]- 結合:
[1, 2, 3] + [4] + [5, 6, 7, 8]
再帰の各レベルで n 要素を 1 度ずつ走査するので、再帰の深さが log n のときは O(n log n)。深さが n (例えばソート済み入力で末尾ピボット選択) になると O(n^2) です。
図のポイント (テキスト併記)
-
「ピボットを基準に小・等・大に分ける」 — クイックソートの心臓部はこれだけ
「ピボットを基準に小・等・大に分ける」 — クイックソートの心臓部はこれだけ。
Python での実装 (シンプル版)
Python
def quickSort(arr):
if len(arr) <= 1:
return list(arr)
pivot = arr[len(arr) // 2]
less = [x for x in arr if x < pivot]
equal = [x for x in arr if x == pivot]
greater = [x for x in arr if x > pivot]
return quickSort(less) + equal + quickSort(greater)リスト内包表記で 3 つに分ける書き方は 3-way partition と呼ばれ、重複要素が多い配列でも効率が落ちません。コードも教科書的でわかりやすい。
JavaScript での実装
JavaScript
function quickSort(arr) {
if (arr.length <= 1) return [...arr];
const pivot = arr[Math.floor(arr.length / 2)];
const less = arr.filter(x => x < pivot);
const equal = arr.filter(x => x === pivot);
const greater = arr.filter(x => x > pivot);
return [...quickSort(less), ...equal, ...quickSort(greater)];
}ピボット選択の戦略
- 末尾 / 先頭固定: 実装最短だが、整列済み入力で最悪化する
- 中央: 多くのケースで安定。ただし悪意ある入力に弱い
- 乱数: 期待値
O(n log n)を保証できる median-of-three: 先頭・中央・末尾の 3 値の中央値を選ぶ。実用ライブラリで多用される
ピボット選択は性能の生命線。本番では
中央か乱数かmedian-of-threeを使うことが多い。
マージソートとの比較
| 観点 | クイックソート | マージソート |
|---|---|---|
| 平均計算量 | O(n log n) | O(n log n) |
| 最悪計算量 | O(n^2) | O(n log n) |
| 空間計算量 | O(log n) (in-place実装の場合、再帰スタックのみ) | O(n) |
| 安定 | 不安定 | 安定 |
| キャッシュ効率 | 良い | 普通 |
よくある間違い
1 つ目は ピボットの除外漏れ。less と greater だけにすると、ピボット自身がどこにも入らずに消える、もしくは無限再帰します。equal を別に作るか、ピボットを 1 つだけ別配列にしておくこと。2 つ目は 同じ値ばかりの配列。3-way partition なら equal に全部入って再帰しないので問題なし。1-pivot Lomuto では O(n^2) に劣化します。3 つ目は 停止条件。<= 1 を忘れて空配列で死ぬパターン。
やってみよう
[3, 3, 3, 3, 3]のような全部同じ配列で、3-way 版と 2-way 版の比較回数を比べてみる。- ピボットを乱数にして、ソート済み入力でも
O(n log n)を保てるか確認する。 - 中央以外のピボット (
arr[0],arr[-1]) でも動作することを試す。
よくある質問
Q. クイックソートの最悪計算量は？
A. O(n²) です。ピボットが常に最小・最大を選んでしまう場合に起きます。ピボットをランダムに選ぶか中央値の中央値を使うとほぼ起きません。実用ライブラリ（Java の Arrays.sort 等）は最悪を避ける工夫が組み込まれています。
Q. 再帰の深さでスタックオーバーフローしませんか？
A. ランダムピボットなら平均 O(log n) の深さで問題ありません。最悪 O(n) になる場合に備え、片側だけ再帰し残りはループにする tail-recursion 最適化がよく使われます。本格的な実装ではループ＋スタック構造で書き換えます。
Q. クイックソートとマージソートはどう使い分けますか？
A. クイックソートはメモリ効率（in-place）と平均速度で勝ち、マージソートは最悪 O(n log n) 保証と安定性で勝ちます。Java は両方を採用しており、参照型は安定性が必要なため TimSort（マージソート派生）を使う実装です。
次のレッスン
次は カウントソート で、ピボットを基準に左右に分けて再帰的にソートするクイックソートを実装する を学びます。
事前確認 — 進む前に次の 3 つができることを確認しましょう。
- クイックソート の要点を自分の言葉で説明できる
- このレッスンの最小コード (または操作手順) を見ずに書ける
- 練習問題やクイズで間違えた箇所を読み直して理解した
理解度チェック (30 秒)
Q. クイックソート とは何か、1 文で説明してください。
A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。
関連レッスン
要件
- 組み込みのソート関数 (Python の sorted, JS の sort, Go の sort.Slice) は使わない
- ピボットを選んで less / equal / greater に分割し、再帰的にソートする
- 戻り値は新しい配列で、入力 arr を破壊的に書き換えない
入出力例
test-cases.txt
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]