クイックソートとは？仕組み・計算量・ピボット選びと実装最適化ガイド

クイックソートとは

クイックソート（Quicksort）は、比較ベースの代表的なソートアルゴリズムの一つで、分割統治法（divide and conquer）に基づいて配列やリストを効率的にソートします。1960年にTony Hoareによって発表され、平均的に非常に高速でメモリ効率も良いため、実務のソート実装や標準ライブラリの核として広く用いられてきました。

基本的な考え方

クイックソートは次の3つのステップで動作します。

• 基準となる要素（ピボット）をひとつ選ぶ。
• 配列をピボットより小さい部分とピボットより大きい部分に分割（パーティション）する。
• 分割された各部分に対して再帰的に同じ処理を行う。

最終的に各部分が長さ0または1になればソートは完了します。分割と再帰を繰り返すことで全体が整列されます。

パーティション方式の代表例

パーティションの実装方法はいくつかあります。代表的な方式は以下の通りです。

• Hoareのパーティション：左右からポインタを進めて交換する方式。移動・交換の回数が少なく効率的で、初期実装（Hoare, 1962）で用いられます。ただし実装上の境界処理に注意が必要です。
• Lomutoのパーティション：単一の走査で、小さい要素を左に集める簡潔な方式。実装は簡単ですが、等値要素や逆順などで交換回数が増えがちです。
• 三分割（Dutch National Flag）パーティション：ピボットと等しい要素を中央にまとめ、ピボット未満・等しい・以上の三領域に分ける方式。重複要素が多い場合に特に有効で、三方向クイックソート（Dijkstraの方式）として知られます。

計算量と空間計算量

クイックソートの時間計算量はピボットの選び方に依存します。

• 平均ケース：O(n log n)。平均的な比較回数は漸近的に約 2 n ln n（≒1.386 n log2 n）です。
• 最良ケース：O(n log n)。常にほぼ半分に分割できる理想状態。
• 最悪ケース：O(n²)。すでに整列済みや逆順で常に最小/最大をピボットに選ぶと生じる。ランダム化や工夫で回避可能。

空間計算量は基本的にインプレースで動作するため追加配列は不要であり、再帰の深さに伴うスタック領域が問題になります。

• 平均の再帰深さ：O(log n)、したがって追加空間は O(log n)。
• 最悪の再帰深さ：O(n)、この場合はスタックオーバーフローの恐れあり。

ピボット選択と最悪ケース回避

ピボットの選択が性能に大きく影響します。一般的な工夫は次の通りです。

• ランダム化（Randomized Quicksort）：ピボットをランダムに選ぶことで、特定の入力に対する最悪ケース発生確率を著しく低下させます。理論的に期待時間は O(n log n) です。
• 三者選択（Median-of-three）：配列の先頭、中間、末尾の3つから中央値をピボットに選ぶことで、整列済み入力での極端な偏りを緩和します。
• 厳密中央値の近似：選択アルゴリズムを用いてより良いピボットを得る方法もありますが、オーバーヘッドが増えるため実装ではトレードオフがあります。

実装上の最適化と実用上の工夫

実際の実装では下記の最適化がよく使われます。

• 小さい区間では挿入ソートに切り替える：例えば閾値を16や32にして、その下では高速な挿入ソートにすることで定数因子を改善。
• 三方向パーティション：同一キーが多いときに有効で、性能を大幅に改善する。
• 尾再帰最適化（tail recursion elimination）：再帰呼び出しを1つに抑え、深さを最小限にすることでスタック使用を低減。
• ランダムピボットの利用：データに依存した最悪ケースを避ける。

安定性（stable）について

標準的なクイックソートは安定ではありません。つまり、等しいキー間の元の順序を保持しません。安定なクイックソートを実現するには追加のメモリを使って要素をグループ化するか、安定なマージ操作など別の手法を組み合わせる必要があります。

ライブラリでの採用例と発展

多くの標準ライブラリではクイックソート由来のアルゴリズムか、その改良版が使われていますが、直接の単純クイックソートだけを使うことは少なくなりました。理由は最悪ケース対策や定数因子のためです。

• C++のstd::sort：一般にIntrosort（クイックソート＋ヒープソートのフォールバック）を採用し、最悪ケースでも O(n log n) を保証します。
• Java（Primitive配列）のArrays.sort：歴史的には様々な手法が使われてきました。Oracle JDKではデュアルピボットクイックソート（V. Yaroslavskiyの手法）が一時期採用され、実行速度の改善が報告されています。一方でオブジェクト配列には安定なTimSortが使われています。

クイックソートと他のソートとの比較

• マージソート（Merge Sort）：安定で最悪ケースO(n log n)を保証するが、追加の線形メモリが必要（インプレース変種もあるが複雑）。
• ヒープソート（Heap Sort）：インプレースで最悪ケースO(n log n)を保証するが、実際の平均性能はクイックソートより劣ることが多い（定数因子の差）。
• Timsort：実データ（部分的にソートされた配列）に対して高性能。多くの高水準言語の標準ソート実装で採用。
• Introsort：クイックソートの高速性とヒープソートの最悪ケース保証を組み合わせ、一般用途で高い性能と安全性を両立。

並列化・外部メモリでの利用

クイックソートは分割後の独立した部分配列に対して独立に処理できるため、並列化に適しています。マルチコア環境では分割作業を複数スレッドで並列実行することで性能向上が期待できます。ただし作業の細分化や負荷分散、メモリ帯域の制約に注意が必要です。

外部メモリ（ディスク）を使うソートでは、クイックソート単体は向きません。ディスクアクセスを最小化するためにマージベースの外部ソート（外部マージソート）が一般に用いられます。

実装でよくある注意点

• ピボットの選び方に注意しないと最悪ケースに陥る。ランダム化やmedian-of-threeは実践的な対策。
• 等値要素が多いデータでは三分割パーティションを用いると著しい改善がある。
• 再帰深度が大きくなり得るため、尾再帰の最適化や小距離では挿入ソートに切り替える工夫が必要。
• 多くのライブラリ実装は単純なクイックソートではなく、複数の最適化を組み合わせて安定性や最悪ケースを補っている。

まとめ

クイックソートは平均的な実行速度が非常に良く、メモリ効率も高いので実用上非常に有用なソートアルゴリズムです。しかしピボット選択や等値の扱い、再帰深度などの実装上の落とし穴があるため、実運用ではランダム化、三分割パーティション、挿入ソート併用、あるいはIntrosortのようなフォールバック機構を組み合わせるのが一般的です。用途やデータ特性に応じて適切なバリエーションや代替アルゴリズムを選ぶことが重要です。

参考文献

Quicksort - Wikipedia
C. A. R. Hoare, "Quicksort", Communications of the ACM, 1962
Introsort - Wikipedia
Quicksort notes (教育資料）
三分割パーティション（Dijkstra）や最適化に関する資料
J. L. Bentley and M. D. McIlroy, "Engineering a Sort Function"（ソート実装上の工夫）
Java Arrays.sort のドキュメント（実装概略）
std::sort (C++) - cppreference