ピボット未満の値を左、以上の値を右へ分け、それぞれを再帰的に整列します。分割によってピボットの最終位置が確定します。

分割と呼び出しスタックを示すクイックソートシミュレーター

再生・ステップ実行・スライダーで操作できます。右端をピボットにするこの実装では、「整列済み」が最悪の場合になります。

最良O(n log n)

平均O(n log n)

最悪O(n²)

追加領域O(log n)

安定いいえ

一般的な性能高速

iとjによる分割

jは未処理の値を走査し、iはピボット未満の値を置く次の位置です。緑のlo…i−1はピボット未満、赤のi…j−1はピボット以上です。最後に両区間の境界iへピボットを移します。

最悪の場合

整列済み入力で右端を選ぶと常に最大値となり、片側がほとんど縮まりません。深さはn、比較回数はn(n−1)/2になります。実用的な実装ではランダムなピボット、3要素の中央値、別アルゴリズムへの切り替えなどを使います。

演習：クイックセレクト

分割後のピボット位置iがkなら、それが求める順序統計量です。異なる場合はkを含む側だけを再帰処理します。適切なピボット選択で期待O(n)になります。通常の整列には sort()、大きい方から少数の値を求める場合には heapq.nsmallest, heapq.nlargestなどを利用できます。