クイックソート¶
クイックソート（quick sort）は分割統治戦略に基づくソートアルゴリズムであり、実行効率が高く、広く利用されています。
クイックソートの中核操作は「パーティション」であり、その目的は、配列内のある要素を「基準数」として選び、基準数より小さいすべての要素を左側へ、大きい要素を右側へ移動することです。具体的には、パーティションの流れを下図に示します。
- 配列の最左端の要素を基準数として選び、2 つのポインタ
iとjを初期化して、それぞれ配列の両端を指すようにします。 - ループを設定し、各ラウンドで
i（j）を使ってそれぞれ基準数より大きい（小さい）最初の要素を探し、その後この 2 つの要素を交換します。 iとjが出会うまでステップ2.を繰り返し、最後に基準数を 2 つの部分配列の境界へ交換します。
パーティションが完了すると、元の配列は左部分配列、基準数、右部分配列の 3 つに分けられ、「左部分配列の任意の要素 \(\leq\) 基準数 \(\leq\) 右部分配列の任意の要素」を満たします。したがって、次はこの 2 つの部分配列だけをソートすれば済みます。
クイックソートの分割統治戦略
パーティションの本質は、長い配列のソート問題を 2 つの短い配列のソート問題へ簡略化することです。
アルゴリズムの流れ¶
クイックソート全体の流れを下図に示します。
- まず、元の配列に対して 1 回「パーティション」を実行し、未ソートの左部分配列と右部分配列を得ます。
- 次に、左部分配列と右部分配列に対してそれぞれ再帰的に「パーティション」を実行します。
- 部分配列の長さが 1 になるまで再帰を続け、配列全体のソートを完了します。
アルゴリズムの特性¶
- 時間計算量は \(O(n \log n)\)、非適応型ソート：平均的な場合、パーティションの再帰の深さは \(\log n\) で、各層の総ループ回数は \(n\) のため、全体で \(O(n \log n)\) 時間を要します。最悪の場合、各回のパーティション操作で長さ \(n\) の配列が長さ \(0\) と \(n - 1\) の 2 つの部分配列に分割され、このとき再帰の深さは \(n\) に達し、各層のループ回数は \(n\) となるため、全体で \(O(n^2)\) 時間を要します。
- 空間計算量は \(O(n)\)、インプレースソート：入力配列が完全な逆順の場合、最悪の再帰深さ \(n\) に達し、\(O(n)\) のスタックフレーム空間を使用します。ソート操作は元の配列上で行われ、追加の配列は用いません。
- 非安定ソート：パーティションの最後のステップで、基準数が等しい要素の右側へ交換される可能性があります。
クイックソートが速い理由¶
名前からも分かるように、クイックソートは効率面で一定の優位性を持っています。クイックソートの平均時間計算量は「マージソート」や「ヒープソート」と同じですが、通常はクイックソートのほうが高効率であり、主な理由は次のとおりです。
- 最悪ケースが起こる確率が低い：クイックソートの最悪時間計算量は \(O(n^2)\) で、「マージソート」ほど安定ではありませんが、大半のケースでは \(O(n \log n)\) の時間計算量で動作します。
- キャッシュ利用効率が高い：パーティション操作の実行時には、システムが部分配列全体をキャッシュに読み込めるため、要素アクセスの効率が高くなります。一方、「ヒープソート」のようなアルゴリズムは要素へ飛び飛びにアクセスする必要があり、この性質を持ちません。
- 計算量の定数係数が小さい：上記 3 つのアルゴリズムの中で、クイックソートは比較、代入、交換などの操作総数が最も少なくなります。これは「挿入ソート」が「バブルソート」より速い理由と似ています。
基準数の最適化¶
クイックソートは、入力によっては時間効率が低下する可能性があります。極端な例として、入力配列が完全な逆順であるとします。最左端の要素を基準数として選ぶため、パーティション完了後には基準数が配列の最右端へ交換され、左部分配列の長さが \(n - 1\)、右部分配列の長さが \(0\) になります。この再帰を続けると、各回のパーティション後に必ず一方の部分配列の長さが \(0\) となり、分割統治戦略が機能せず、クイックソートは「バブルソート」に近い形へ退化します。
この状況をできるだけ避けるため、パーティションにおける基準数の選び方を最適化できます。たとえば、ランダムに 1 つの要素を選んで基準数にできます。しかし、運が悪く毎回望ましくない基準数を選んでしまうと、効率は依然として十分ではありません。
注意すべき点として、プログラミング言語が通常生成するのは「疑似乱数」です。疑似乱数列に合わせて特定のテストケースを構築すると、クイックソートの効率はやはり劣化する可能性があります。
さらに改善するために、配列から 3 つの候補要素（通常は先頭、末尾、中間の要素）を選び、**その 3 つの候補要素の中央値を基準数とする**ことができます。こうすると、基準数が「小さすぎず大きすぎもしない」確率が大幅に上がります。もちろん、候補要素をさらに増やして、アルゴリズムの頑健性をいっそう高めることも可能です。この方法を採用すると、時間計算量が \(O(n^2)\) まで劣化する確率は大きく下がります。
コード例を以下に示します。
再帰の深さの最適化¶
一部の入力では、クイックソートは多くの空間を消費する可能性があります。完全に整列済みの入力配列を例にとり、再帰中の部分配列の長さを \(m\) とします。各回のパーティション操作では長さ \(0\) の左部分配列と長さ \(m - 1\) の右部分配列が生成されます。これは、各再帰呼び出しで減る問題サイズが非常に小さいこと（要素が 1 つ減るだけ）を意味し、再帰木の高さは \(n - 1\) に達するため、このとき \(O(n)\) のスタックフレーム空間を占有します。
スタックフレーム空間の蓄積を防ぐために、各回のパーティション完了後に 2 つの部分配列の長さを比較し、**短いほうの部分配列に対してのみ再帰**を行えます。短い部分配列の長さは \(n / 2\) を超えないため、この方法なら再帰の深さを \(\log n\) 以下に抑えられ、最悪時の空間計算量を \(O(\log n)\) まで最適化できます。コードを以下に示します。