ピボットを境に問題を分ける
クイックソートは、ピボットと呼ぶ基準値を選び、その値より小さい要素と大きい要素へ範囲を分け、それぞれを再帰的に整列します。分割が終わっても、左右それぞれの内部はまだ整列していない点が重要です。ピボットの選び方や、同じ値をどこへ置くか、分割を配列内で行うかによって多くの変種があります。二方向分割と、同値の範囲を分離する三方向分割も区別します。
[4,1,3,2]を3で分ける
ピボットを3とすれば、小さい側は[1,2]、等しい側は[3]、大きい側は[4]と考えられます。この例では左右が小さくなり、残る処理も少なくなります。これは分割結果を説明する概念的な例であり、実際の配列内分割が必ずこの順序を作るという意味ではありません。分割処理では、既に条件を満たす領域と未処理領域を分け、交換のたびに境界を更新していきます。
良い分割と悪い分割
各回の分割がほどよく釣り合えば、段数はO(log n)、各段の処理合計はO(n)となります。ランダムなピボット選択などの仮定により、期待O(n log n)と評価できます。一方、昇順データで常に最小の先頭値をピボットにする素朴な方式では、0要素とn−1要素へ偏り続け、仕事の和がn+(n−1)+…となり最悪O(n²)です。平均・期待の評価を、無条件の最悪保証に読み替えないようにします。
安定性とスタックも確認する
典型的な配列内分割では、等しいキーの元の順序は保証されず、安定整列ではありません。安定性が必要なら別の方式や変種を選びます。また、配列外の大きなマージ領域を使わない実装でも、再帰呼び出しのスタックは必要です。再帰が偏るとスタックも増えるため、小さい側だけ再帰して大きい側を反復処理するなどの工夫があります。比較回数だけでなく、同値の多さ、ピボット方式、メモリ条件を含めて実装を選びます。