クイックソート

クイックソート
クイックソートアルゴリズムのアニメーションによる視覚化。水平線はピボット値です。
クラスソートアルゴリズム
最悪のパフォーマンスお（n2）{\displaystyle O(n^{2})}
最高のパフォーマンスお（nログ⁡n）{\displaystyle O(n\log n)}(単純なパーティション)または(3 方向のパーティションと等しいキー)お（n）{\displaystyle O(n)}
平均的なパフォーマンスお（nログ⁡n）{\displaystyle O(n\log n)}
最悪の場合の空間複雑度お（n）{\displaystyle O(n)}補助的（素朴）補助的（Hoare 1962）お（ログ⁡n）{\displaystyle O(\log n)}
最適いいえ

クイックソートは、効率的で汎用的なソートアルゴリズムです。クイックソートは、イギリスのコンピュータ科学者トニー・ホーアによって1959年に開発され[ 1 ]、1961年に公開されました[ 2 ]。現在でもソートアルゴリズムとして広く使用されています。全体的に見て、ランダム化されたデータ、特に大規模な分布の場合、マージソートやヒープソートよりもわずかに高速です[ 3 ] 。

クイックソートは分割統治アルゴリズムです。配列から「ピボット」要素を選択し、残りの要素をピボットより小さいか大きいかに基づいて2つのサブ配列に分割することで動作します。このため、クイックソートは分割交換ソートと呼ばれることもあります。[ 4 ]次に、サブ配列を再帰的にソートします。これはインプレースで実行でき、ソートを実行するために 少量の追加メモリを必要とします。

クイックソートは比較ソートの一種であり、つまり「より小さい」関係（正式には全順序）が定義されている任意の型の項目をソートできます。要素aとbは、それらの相対的な順序が以前の比較結果の推移閉包によって得られた場合にのみ交換されるため、比較ベースのソートです。クイックソートの実装のほとんどは安定的ではなく、つまり、同じソート項目の相対的な順序は保持されません。

クイックソートの数学的分析によると、平均すると、このアルゴリズムはn個の項目をソートするのに比較を回行う。最悪の場合、比較は 回行われる。 お（nログ⁡n）{\displaystyle O(n\log {n})}お（n2）{\displaystyle O(n^{2})}

歴史

クイックソートアルゴリズムは、1959年にモスクワ国立大学の客員学生だったトニー・ホーアによって開発されました。当時、ホーアは国立物理学研究所の機械翻訳プロジェクトに携わっていました。翻訳プロセスの一環として、磁気テープ上にアルファベット順に記録された露英辞書でロシア語の文章中の単語を検索する前に、その単語をソートする必要がありました。[ 5 ]最初のアイデアである挿入ソートが遅いことに気づいた後、彼は新しいアイデアを思いつきました。彼はマーキュリーオートコードでパーティション部分を記述しましたが、ソートされていないセグメントのリストの処理に問題がありました。イギリスに戻ると、彼はシェルソートのコードを書くように依頼されました。ホーアは上司に、より高速なアルゴリズムを知っていると伝えたところ、上司はそれを知らないと賭けました。上司は最終的に、ホーアが賭けに負けたことを認めました。ホーアは、このアルゴリズムに関する論文を、1962年に『コンピュータジャーナル』第5巻第1号の10～16ページで発表しました。その後、ホーアはALGOLとその再帰機能について学び、その改良版のアルゴリズムを、当時のトップクラスのコンピュータサイエンス雑誌であるCommunications of the Association for Computing Machinery誌に掲載することができた。 [ 2 ] [ 6 ] ALGOLのコードは、Communications of the ACM (CACM)、第4巻、1961年7月発行、321ページの「アルゴリズム63: パーティション」および「アルゴリズム64: クイックソート」に掲載されている。

クイックソートは広く採用され、例えばUnixではデフォルトのライブラリソートサブルーチンとして登場しました。そのため、 C言語の標準ライブラリサブルーチンqsort [ 7 ]やJavaのリファレンス実装にもクイックソートの名前が付けられました。

ロバート セジウィックの 1975 年の博士論文はクイックソートの研究におけるマイルストーンであると考えられており、サンプルソート、ヴァン エムデンによる適応型分割[ 8 ] 、比較とスワップの期待数の導出など、さまざまなピボット選択スキームの分析に関連する多くの未解決の問題を解決しました。[ 7 ]ジョン ベントレーとダグ マキロイは 1993 年に、等しい要素を処理する手法や、9 個の要素のサンプルを 3 つのグループに分割し、3 つのグループから 3 つの中央値の中央値を選択する、疑似中央値 9 と呼ばれるピボット スキームなど、プログラミング ライブラリで使用するためにさまざまな改良を取り入れました。 [ 7 ]ベントレーは、ニコ ロミュートに帰属する著書Programming Pearlsで、より単純でコンパクトな分割スキームについて説明しました。[ 9 ]ベントレーは同じエッセイの中でクイックソートを「私が今まで書いた中で最も美しいコード」と評している。ロミュートの分割方式も教科書『アルゴリズム入門』で広く知られるようになったが、平均して3倍のスワップが発生し、すべての要素が等しい場合、実行時間がO ( n^ 2 )に低下するため、ホーアの方式よりも劣っている。[ 10 ]マキロイはさらに1998年にアンチクイックソート（aqsort ）関数を開発し、この関数は敵対的なデータをオンザフライで生成することで、1993年のクイックソートの変種でさえも一貫して二次関数的な挙動を見せる。[ 11 ]

アルゴリズム

ランダムな数値集合に対するクイックソートの完全な例。網掛けの要素がピボットです。これは常にパーティションの最後の要素として選択されます。しかし、このようにパーティションの最後の要素を常にピボットとして選択すると、既にソート済みの配列、または同一要素の配列ではパフォーマンスが低下します（ O ( n2 )）。大規模な数値集合に対するソート処理の終盤では、ソート済み/同一要素のサブ配列が頻繁に出現するため、ピボットを中央の要素として選択するクイックソートアルゴリズムは、この図で説明されているアルゴリズムよりも、大規模な数値集合に対してはるかに高速に実行されます。

クイックソートは、分割ルーチンに基づいて配列をソートする分割統治アルゴリズムの一種です。この分割の詳細は多少異なるため、クイックソートは実際には密接に関連したアルゴリズムの集合体です。2つ以上の要素を含む範囲に分割を適用すると、最初の範囲のどの要素も2番目の範囲のどの要素よりも大きくならないような、連続する2つの空でない部分範囲への分割が生成されます。この分割を適用した後、クイックソートは部分範囲を再帰的にソートします。この際、分割時点で既に最終的な位置にあることが分かっている要素を除外する場合もあります。クイックソートは再帰的な性質を持つため、最終的な目標が配列全体をソートすることであっても、（分割ルーチンと同様に）より大きな配列内の範囲に対して呼び出し可能に設計する必要があります。インプレース・クイックソートの手順は次のとおりです。

  1. 範囲の要素数が2未満の場合、何もする必要がないため、直ちに戻ります。それ以外の非常に短い長さの場合は、特殊なソート方法が適用され、残りの手順はスキップされる可能性があります。
  2. それ以外の場合は、範囲内で発生するピボットと呼ばれる値を選択します(選択の正確な方法はパーティション ルーチンによって異なり、ランダム性が含まれる場合があります)。
  3. 範囲を分割します。分割点を決定しながら、要素を並べ替えます。ピボットより小さい値を持つすべての要素は分割点の前に配置され、ピボットより大きい値を持つすべての要素は分割点の後に配置されます。ピボットと等しい要素はどちら側にも配置できます。ピボットのインスタンスが少なくとも1つ存在するため、ほとんどの分割ルーチンは、分割点の値がピボットと等しく、最終的な位置にあることを保証します（ただし、元の値よりも厳密に小さいサブ範囲が生成されている限り、クイックソートの終了はこれに依存しません）。
  4. 分割点までのサブ範囲と分割点以降のサブ範囲にクイックソートを再帰的に適用し、分割点におけるピボットに等しい要素を両方の範囲から除外する場合もあります。（分割によって境界付近に、すべての要素がピボットに等しいことが分かっているより大きなサブ範囲が生成される可能性がある場合は、それらも除外できます。）

分割ルーチンの選択（ピボットの選択を含む）や、上記で完全には規定されていないその他の詳細は、アルゴリズムのパフォーマンスに影響を与える可能性があり、特定の入力配列では大きな影響を与える可能性があります。したがって、クイックソートの効率性を議論するには、まずこれらの選択を明確にする必要があります。ここでは、2つの具体的な分割手法について説明します。

ロミュート分割方式

この方式はニコ・ロミュートによるものとされ、ベントレーの著書Programming Pearls [ 12 ]とコーメンらの著書Introduction to Algorithms [ 13 ]によって普及しました。ほとんどの定式化では、この方式は配列の最後の要素をピボットとして選択します。アルゴリズムは、別のインデックスjを使用して配列をスキャンするときにインデックスiを維持し、 loからi-1 (両端を含む)の要素がピボットより小さく、iからj (両端を含む) の要素がピボットと等しいかそれより大きくなります。この方式はよりコンパクトで理解しやすいため、入門資料で頻繁に使用されますが、たとえばすべての要素が等しい場合など、ホーアの元の方式ほど効率的ではありません。[ 14 ]配列がすでに順序付けられている場合、この方式によるクイックソートの複雑度は、パーティションが最悪のものになるため、 O ( n 2 )に低下します。[ 10 ]パフォーマンスを向上させるために、ピボットの選択方法、等しい要素の扱い方、小さな配列に対する挿入ソートなどの他のソートアルゴリズムの使用など、様々なバリエーションが提案されている。擬似コードでは、配列Aのloからhiまでの要素（両端を含む）をソートするクイックソートは次のように表される。[ 13 ]

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートするアルゴリズムquicksort(A, lo, hi)は// インデックスが正しい順序であることを確認するif lo >= hi || lo < 0 then 戻る // 配列を分割してピボットインデックスを取得する p := パーティション(A, lo, hi) // 2つのパーティションをソートする quicksort(A, lo, p - 1) // ピボットの左側 quicksort(A, p + 1, hi) // ピボットの右側// 配列を2つのパーティションに分割します。アルゴリズムpartition(A, lo, hi)は pivot:=A[hi]です。 // 最後の要素をピボットとして選択します。// 一時的なピボットインデックス 私 := lo for j := lo to hi - 1 do // 現在の要素がピボット以下の場合if A[j] <= pivot then // 現在の要素を一時ピボットインデックスの要素と交換 swap A[i] with A[j] // 一時ピボットインデックスを前方に移動する i := i + 1 // ピボットを最後の要素と交換する swap A[i] with A[hi] return i // ピボットのインデックス

配列全体のソートはquicksort(A, 0, length(A) - 1)によって実行されます。

ホーア分割方式

ホーアの分割法を用いたクイックソートのアニメーションデモ。赤い枠線は左と右のポインタの位置（それぞれiとj）、黒い枠線はソートされた要素の位置、塗りつぶされた黒い四角は比較対象となる値（pivot）を示しています。

トニー・ホーアが説明したオリジナルの分割スキームでは、分割する配列の両端から始まり、互いに近づきつつ反転を検出するまで進む 2 つのポインタ (範囲のインデックス) を使用します。反転とは、最初のポインタのピボットよりも大きい要素と、2 番目のポインタのピボットよりも小さい要素のペアです。この時点で最初のポインタがまだ 2 番目のポインタよりも前にある場合、これらの要素は互いの順序が間違っているため、交換されます。[ 15 ]この後、ポインタは内側に移動され、反転の検索が繰り返されます。最終的にポインタが交差すると (最初のポインタが 2 番目のポインタの後を指す)、交換は実行されません。交差したポインタの間に分割点がある有効な分割が見つかります (交差したポインタの間に厳密に存在する可能性のあるエントリはピボットと等しく、形成される両方のサブ範囲から除外できます)。この定式化では、1 つのサブ範囲が元の範囲全体になる可能性があり、その場合はアルゴリズムが先に進めなくなります。したがって、ホーアは、最後に、ピボット要素 (まだ元の位置にある) を含むサブ範囲のサイズを、そのピボットを除外し、必要に応じてそれを分離に最も近いサブ範囲要素と交換することによって縮小できることを規定しています。これにより、クイックソートの終了が保証されます。

この元の記述に関して、実装では些細ではあるものの重要な変更が加えられることがよくあります。特に、以下に示すスキームでは、反転の候補にピボットに等しい要素が含まれています（したがって、「より大きい」および「より小さい」の代わりに、それぞれ「以上」および「以下」のテストが使用されています。これは、定式化ではrepeat ... untilではなくdo ... whileを使用しているためです。これは、厳密な比較演算子の使用によって反映されています）。ピボットに等しい要素を交換する理由はありませんが、この変更により、ポインタ自体のテストを省略できます。このテストは、範囲外にならないようにするために必要です。実際、範囲内にピボット値のインスタンスが少なくとも1つ存在するため、包含テストを使用する場合、どちらのポインタの最初の前進もこのインスタンスを越えることはできません。交換が実行されると、交換されたこれらの要素は両方とも、それらを見つけたポインタよりも厳密に前方に位置するため、そのポインタが飛び出すのを防ぎます。 （後者は使用するテストとは独立して成り立つため、最初の反転を探す場合にのみ包括的テストを使用することが可能です。ただし、包括的テストを全体にわたって使用することで、範囲内のすべての要素が等しい場合に中央付近の分割が確実に検出され、多くの等しい要素を持つ配列のソートにおいて重要な効率性の向上がもたらされます。）前進しない分離が生じるリスクは、Hoare が説明した方法とは異なる方法で回避されます。このような分離は、反転が見つからず、両方のポインタが最初の反復でピボット要素まで前進する場合にのみ発生します（その場合、ポインタは交差したと見なされ、交換は発生しません）。

擬似コードでは、[ 13 ]

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートするアルゴリズムquicksort(A, lo, hi)は、 lo >= 0 && hi >= 0 && lo < hiの場合、 p := パーティション(A, lo, hi) quicksort(A, lo, p) // 注: ピボットが含まれるようになりました クイックソート(A, p + 1, hi) // 配列を2つのパーティションに分割します。アルゴリズムpartition(A, lo, hi)は、 // ピボット値 pivot:=A[lo]です。 // 最初の要素をピボットとして選択します。// 左インデックス i := lo - 1 // 右インデックス j := hi + 1 永久にループする// 左のインデックスを少なくとも1回右に移動し、左のインデックスの要素がピボットより小さい間、i := i + 1 を実行する(A[i] < pivot)// 右インデックスを少なくとも1回左に移動し、右インデックスの要素がピボットよりも大きい 間、 A[j] > pivotでj := j - 1 を実行します。// インデックスが交差している場合は、 i >= jの場合は jを返します。// 左と右のインデックスの要素を入れ替える A[i]とA[j] を入れ替える

配列全体はquicksort(A, 0, length(A) - 1)によってソートされます。

Hoare の方式は、平均してスワップが 3 倍少ないため、Lomuto のパーティション方式よりも効率的です。また、前述のように、示された実装では、すべての値が等しい場合でもバランスの取れたパーティションが作成されます。[ 10 ]これは、Lomuto の方式では発生しません。Lomuto のパーティション方式と同様に、Hoare のパーティション分割でも、ピボットが最初または最後の要素として選択された場合、すでにソート済みの入力に対して QuicksortのパフォーマンスがO ( n 2 )に低下します。ただし、中央の要素をピボットにすると、ソートされたデータは同じサイズのパーティションで (ほぼ) スワップなしで生成され、Quicksort の最良の動作、つまりO ( n log( n ))になります。他の方法と同様に、Hoare のパーティション分割では安定したソートは生成されません。この方式では、ピボットの最終的な位置は必ずしも返されるインデックスにあるとは限りません。これは、ピボットとピボットに等しい要素がパーティションステップの後にパーティション内の任意の位置に存在する可能性があり、再帰によって単一要素のパーティションの基本ケースに到達するまでソートされない可能性があるためです。したがって、メインアルゴリズムが再帰する次の2つのセグメントは、 Lomutoの方式の(lo..p-1)と(p+1..hi )ではなく、 ( lo..p ) (要素≤ピボット)と(p+1..hi) (要素≥ピボット)です。

後続の再帰（前の段落の拡張）

メインアルゴリズムが再帰的に実行する次の2つのセグメントについて、もう少し詳しく説明しましょう。「do...while」ループでは、範囲外にならないように厳密な比較演算子（>、<）を使用しているため、ピボット自体がパーティション関数内の他の要素と入れ替わる可能性があります。そのため、パーティション関数で返されるインデックスは、必ずしも実際のピボットの位置を示すとは限りません。[5, 2, 3, 1, 0]の例を考えてみましょう。このスキームに従うと、最初のパーティションの後、配列は[0, 2, 1, 3, 5]になり、返される「インデックス」は2、つまり1になります。実際のピボット、つまりパーティションの開始点として選択したのは3です。この例から、パーティション関数で返されたインデックスを後続の再帰に含める必要があることがわかります。結果として、(lo..p)と(p+1..hi)を再帰的に処理するか、(lo..p-1)と(p..hi)を再帰的に処理するかという選択肢が提示されます。どちらの選択肢を選ぶかは、インデックスが交差する際にパーティション関数でどのインデックス（iまたはj）を返すか、そしてパーティション関数でピボットをどのように選択するか（floorまたはceiling）によって決まります。

まず、複数の同一要素が存在する配列[0, 0]をソートする例を用いて、 (lo..p)と(p+1..hi)の再帰処理の選択について検討します。分割関数でインデックスが交差した後にインデックス i（「後者」のインデックス）が返される場合、最初の分割後にはインデックス 1 が返されます。その後の(lo..p)の再帰は(0, 1) で行われ、これは全く同じ配列[0, 0]に対応します。これにより、無限再帰を引き起こす非前進的な分割が生成されます。したがって、(lo..p)と(p+1..hi)の再帰処理では、再帰の左半分に返されたインデックスが含まれるため、非前進的なシナリオにおいて「末尾」を除外するのは分割関数の役割であることは明らかです。つまり、インデックス i ではなく、インデックス j（インデックスが交差する際の「前者」のインデックス）が返される必要があります。同様の論理で、既にソート済みの配列[0, 1]の例を考えてみると、ポインタが「後者」ではなく「前者」で停止することを保証するには、ピボットを「floor」にする必要があります（ピボットを「ceiling」にすると、インデックス1が返され、(lo..p)に含まれてしまい、無限再帰が発生します）。これは、最後の要素をピボットとして選択することを避けるべき理由と全く同じです。

(lo..p-1)と(p..hi)の再帰の選択は、上記と全く同じ論理に従います。再帰の右半分には返されたインデックスが含まれるため、非前進シナリオにおいて「ヘッド」を除外するのはパーティション関数の役割です。パーティション関数では、インデックス i（インデックスが交差した後の「後ろの」インデックス）を返す必要があり、「天井」をピボットとして選択する必要があります。複数の同一要素が存在する配列 ( [0, 0] ) をソートする例と、既にソート済みの配列[0, 1]をソートする例を考えてみると、この2つのニュアンスは明確になります。再帰のバージョンでは、同じ理由から、最初の要素をピボットとして選択することは避けなければならないことに注意してください。

実装上の問題

ピボットの選択

クイックソートのごく初期のバージョンでは、パーティションの左端の要素がピボット要素として選択されることが多かった。残念ながら、これは既にソート済みの配列において最悪の動作を引き起こすが、これはかなり一般的な使用例である。[ 16 ]この問題は、ピボットにランダムなインデックスを選択するか、パーティションの中央のインデックスを選択するか、（特にパーティションが長い場合は）パーティションの最初、真ん中、最後の要素の中央値をピボットに選択する（Sedgewickの推奨どおり）ことで簡単に解決できた。[ 17 ]この「3つの中央値」ルールは、ソート済み（または逆ソート済み）の入力の場合に有効であり、入力の順序に関する情報が不明な場合に、単一の要素を選択するよりも最適なピボット（真の中央値）をより正確に推定できる。

Lomuto パーティションの 3 つの中央値のコード スニペット: 

mid := ⌊(lo + hi) / 2⌋ もしA[mid] < A[lo]ならば A[lo]とA[mid]を入れ替える A[hi] < A[lo]の場合 A[lo]とA[hi]を入れ替える A[mid] < A[hi]の場合 A[mid]とA[hi]を入れ替える ピボット := A[hi]

最初に中央値を代入しA[hi]、次にその新しい値をA[hi]ピボットとして使用します (これは、上記で示した基本的なアルゴリズムと同様です)。

具体的には、ランダムピボット選択によるn個の要素のソートに必要な比較回数の期待値は（§ 平均ケース分析を参照）、 1.386 n log nである。3の中央値ピボットでは、この値はC n , 2 ≈ 1.188 n log nに減少するが、その代償として、スワップ回数の期待値が3%増加する。[ 7 ]より大きな配列に対するさらに強力なピボットルールは、 9番目の再帰的な3の中央値（Mo3）を選択することである。これは[ 7 ]で定義される。

ninether( a ) = median(Mo3(first ⁠1/3⁠の) , Mo3(中間⁠1/3⁠の) , Mo3(最終⁠1/3⁠の) )

ピボット要素の選択は、整数オーバーフローの存在によっても複雑になります。ソート対象の部分配列の境界インデックスが十分に大きい場合、中間インデックスの単純な式( lo + hi )/2はオーバーフローを引き起こし、無効なピボットインデックスを生成します。これは、例えば中間要素のインデックスにlo + ( hi − lo )/2を使用することで回避できますが、より複雑な演算が必要になります。同様の問題は、ピボット要素を選択する他の方法でも発生します。

繰り返し要素

上で説明した Lomuto 分割方式などの分割アルゴリズムでは (適切なピボット値を選択した場合でも)、多数の重複要素を含む入力に対してクイックソートのパフォーマンスが低下します。この問題は、すべての入力要素が等しい場合に特に顕著になります。つまり、各再帰において、左の分割は空 (ピボットより小さい入力値がない) であり、右の分割は 1 要素だけ減少します (ピボットが削除される)。その結果、Lomuto 分割方式では、等しい値の配列をソートするのに2 乗の時間がかかります。一方、Hoare 分割方式などの分割アルゴリズムでは、重複要素によって一般に分割が改善され、ピボットに等しい要素の不要なスワップが発生する可能性がありますが、重複要素の数が増えるにつれて実行時間は通常減少します (メモリ キャッシュによってスワップのオーバーヘッドが削減されるため)。すべての要素が等しい場合、Hoare 分割方式では要素が不必要にスワップされますが、上記の Hoare 分割のセクションで述べたように、分割自体は最善のケースです。

ロミュート分割問題（オランダ国旗問題とも呼ばれる[ 7 ]）を解くには、値をピボットより小さい値、ピボットと等しい値、ピボットより大きい値の3つのグループに分割する、線形時間の代替分割ルーチンを使用することができます。（ベントレーとマキロイはこれを「ファットパーティション」と呼び、これはUnixバージョン7のqsortで既に実装されていました。[ 7 ]）ピボットと等しい値は既にソートされているため、より小さいパーティションとより大きいパーティションのみを再帰的にソートする必要があります。擬似コードでは、クイックソートアルゴリズムは次のようになります。 

// 配列（の一部）をソートし、それをパーティションに分割し、それらをソートします。アルゴリズムquicksort(A, lo, hi)は、 lo >= 0 && lo < hiの場合 、lt, gt := partition(A, lo, hi)です。// 複数の戻り値 クイックソート(A, lo, lt - 1) クイックソート(A, gt + 1, hi) // 配列を3つのパーティションに分割します。アルゴリズムpartition(A, lo, hi)は、 // ピボット値 pivot:=A[(lo + hi) / 2]です。 // 中央の要素をピボットとして選択します（整数除算）// 小さい、等しい、大きいインデックス lt := lo 等価 := lo gt := こんにちは // すべての要素をピボットと比較しますwhile eq <= gt do if A[eq] < pivot then // 等しいか小さい方のインデックスの要素を交換しますswap A[eq] with A[lt] // 小さい方のインデックスを増やします lt := lt + 1 // 等インデックスを増やす 等価 := 等価 + 1 else if A[eq] > pivot then // 等しいか大きいインデックスの要素を交換しますswap A[eq] with A[gt] // 大きい方のインデックスを減らします gt := gt - 1 else // if A[eq] = pivot then // 等しいインデックスを増やす 等価 := 等価 + 1 // 小さい方と大きい方のインデックスを返すreturn lt, gt

このpartitionアルゴリズムは、中央のパーティションの最初の（「左端」）項目と最後の（「右端」）項目へのインデックスを返します。パーティションの他のすべての項目はピボットと等しいため、ソートされています。したがって、パーティションの項目は への再帰呼び出しに含める必要はありませんquicksort。

このアルゴリズムの最適なケースは、すべての要素が等しい場合（またはk ≪ n個の要素からなる小さな集合から選択された場合）です。すべての要素が等しい場合、修正クイックソートは空の部分配列に対して2回の再帰呼び出しのみを実行し、線形時間で終了します（partitionサブルーチンの実行時間が線形時間を超えないと仮定した場合）。

最適化

セジウィックが提案し、実際に広く使用されている他の重要な最適化は次のとおりです。[ 18 ] [ 19 ]

  • 最大でO (log n ) のスペースが使用されるようにするには、最初にパーティションの小さい側を再帰し、次に末尾呼び出しを使用してもう一方のパーティションを再帰するか、パラメーターを更新して、現在ソートされている小さい側を含まないようにし、大きい側をソートするように繰り返します。
  • 要素数が閾値（例えば10要素）を下回った場合、挿入ソートなどの非再帰ソートアルゴリズムに切り替えます。挿入ソートは、そのような小さな配列に対して、スワップ、比較、その他の操作をより少なく実行します。理想的な「閾値」は、具体的な実装の詳細によって異なります。
  • 以前の最適化の古いバージョンです。要素数が閾値k未満の場合、単に停止し、配列全体を処理した後、挿入ソートを実行します。再帰を早期に停止すると、配列はkソートされた状態になります。つまり、各要素は最終的なソート位置から最大k位置離れていることになります。この場合、挿入ソートはソートを完了するのにO ( kn )時間かかります。これは、 kが定数の場合、線形です。[ 20 ] [ 12 ] : 117 このバージョンは、「多数の小さなソート」最適化と比較して、実行する命令数は少なくなりますが、現代のコンピュータのキャッシュメモリを最適に使用しません。[ 21 ]

並列化

クイックソートの分割統治法による定式化により、タスク並列処理を使用した並列化が容易になります。分割ステップは、並列プレフィックス合計アルゴリズムを使用して、分割された配列の各配列要素のインデックスを計算することで実現されます。[ 22 ] [ 23 ]サイズnの配列が与えられると、分割ステップではO( n ) の作業をO (logn )時間で実行し、 O( n )の追加スクラッチスペースが必要になります。配列が分割された後、 2 つのパーティションを並列で再帰的にソートできます。ピボットの理想的な選択を前提とすると、並列クイックソートはサイズ n の配列を O(nlogn) の作業でソートし、O ( log2n )時間で、O ( n )の追加スペースを使用します。

クイックソートは、マージソートなどの他のソートアルゴリズムと比較していくつかの欠点があり、効率的な並列化が複雑になります。クイックソートの分割統治木の深さはアルゴリズムのスケーラビリティに直接影響し、この深さはアルゴリズムがピボットとして選択する値に大きく依存します。さらに、パーティショニングステップをインプレースで効率的に並列化することは困難です。スクラッチスペースを使用するとパーティショニングステップは簡素化されますが、アルゴリズムのメモリ使用量と一定のオーバーヘッドが増加します。

より洗練された並列ソートアルゴリズムでは、さらに優れた時間制限を達成することができる。[ 24 ]例えば、1991年にDavid MW Powersは、n個のプロセッサを持つCRCW （同時読み取りおよび同時書き込み）PRAM （並列ランダムアクセスマシン）上で暗黙的にパーティショニングを実行することでO（log n）時間で動作できる並列化クイックソート（および関連する基数ソート）について説明した。[ 25 ]

形式分析

最悪のケース分析

最も不均衡な分割は、分割ルーチンによって返されるサブリストの1つのサイズがn − 1である場合に発生します。[ 26 ]これは、ピボットがリスト内の最小または最大の要素である場合、または一部の実装（たとえば、上記のLomuto分割スキーム）ではすべての要素が等しい場合に発生する可能性があります。

これがすべての分割で繰り返し発生する場合、各再帰呼び出しは、前のリストよりもサイズが1小さいリストを処理します。したがって、サイズ1のリストに到達するまでに、n − 1回のネストされた呼び出しが必要になります。これは、呼び出し木がn − 1回のネストされた呼び出しの線形チェーンであることを意味します。i番目の呼び出しは分割を実行するためにO ( n − i )回の作業を行い、したがって、この場合、クイックソートにはO ( n 2 )回の時間がかかります。 ∑私＝0n（n−私）＝お（n2）{\displaystyle \textstyle \sum _{i=0}^{n}(ni)=O(n^{2})}

ベストケース分析

最もバランスの取れたケースでは、各パーティションがリストをほぼ等しい 2 つの部分に分割します。つまり、各再帰呼び出しは半分のサイズのリストを処理します。その結果、サイズ 1 のリストに到達する前に、log 2 n回のネストされた呼び出ししか実行できません。これは、呼び出しツリーの深さがlog 2 nであることを意味します。ただし、呼び出しツリーの同じレベルにある 2 つの呼び出しが、元のリストの同じ部分を処理することはありません。そのため、各レベルの呼び出しに必要な時間は合計でO ( n )時間だけです (各呼び出しには一定のオーバーヘッドがありますが、各レベルでの呼び出しはO ( n )回だけなので、これはO ( n )係数に含まれます)。結果として、アルゴリズムが使用する時間はO ( nlogn )時間だけになります。

平均ケース分析

n個の異なる要素を持つ配列をソートする場合、クイックソートは、等確率でn個の要素を持つn !通りの順列すべてについて平均すると、期待値でO ( nlogn )の時間がかかります。あるいは、アルゴリズムが入力配列からピボットを均一にランダムに選択する場合、同じ分析を用いて任意の入力シーケンスの期待実行時間を制限することができます。この場合、期待値はアルゴリズムによって行われるランダムな選択に適用されます（Cormen et al. , Introduction to Algorithms , [ 13 ]セクション7.3）。

この主張に対する 3 つの一般的な証明では、パーセンタイル、再帰、およびバイナリ検索ツリーが使用され、それぞれがクイックソートの動作に関するさまざまな洞察を提供します。

パーセンタイルの使用

各ピボットのランクが中央の50%、つまり25パーセンタイルと75パーセンタイルの間に位置する場合、要素を両側に25%以上75%以下の割合で分割します。このようなピボットを一貫して選択すると、リストサイズが1になる前にリストを最大回分割するだけで済み、O ( n log n )のアルゴリズムが得られます。 ログ4/3⁡n{\displaystyle \log_{4/3}n}

入力がランダム順列の場合、ピボットのランクはランダムなので、中央 50 パーセントにあるとは限りません。ただし、ランダム順列から開始する場合、各再帰呼び出しのピボットのリスト内のランクはランダムなので、約半分の確率で中央 50 パーセントにあります。コインを投げたところを想像してください。表はピボットのランクが中央 50 パーセントにあることを意味し、裏はそうでないことを意味します。次に、k回表が出るまでコインを何度も投げ続けたところを想像してください。これには長い時間がかかるかもしれませんが、平均して2 k回投げるだけで済み、 100 k回投げてもk回表にならない可能性は非常に低いです (これはチェルノフ境界を使って厳密にすることができます)。同じ議論により、クイックソートの再帰は平均して の呼び出し深度でのみ終了します。しかし、平均呼び出し深度がO (log n )で、呼び出しツリーの各レベルで最大n個の要素が処理される場合、平均して実行される作業量はO ( n log n )の積になります。アルゴリズムは、一定回数実行される限り、ピボットが中央の半分にあることを検証する必要はありません。 2ログ4/3⁡n{\displaystyle 2\log _{4/3}n}

より慎重な議論を用いることで、ピボットがランダムに選択されるクイックソートのバージョンに対してこの証明を拡張し、高い確率で成立する時間制限を示すことができる。具体的には、任意の に対して とすると、少なくとも の確率で、比較回数は を超えない。[ 27 ]1つの≥4{\displaystyle a\geq 4}c＝（1つの−4）/2{\displaystyle c=(a-4)/2}1−1nc{\displaystyle 1-{\frac {1}{n^{c}}}}21つのnログ4/3⁡n{\displaystyle 2an\log _{4/3}n}

繰り返しの使用

代替的なアプローチは、サイズnのリストをソートするのに必要な時間であるT ( n )因子の再帰関係を設定することである。最も不均衡なケースでは、1回のクイックソート呼び出しにO ( n )の作業と、サイズ0とn −1のリストに対する2回の再帰呼び出しが必要となるため、再帰関係は次のようになる。

T（n）＝お（n）+T（0）+T（n−1）＝お（n）+T（n−1）。{\displaystyle T(n)=O(n)+T(0)+T(n-1)=O(n)+T(n-1).}

これは挿入ソートや選択ソートと同じ関係であり、最悪の場合でもT ( n )= O ( n2 )となります。

最もバランスの取れたケースでは、1回のクイックソート呼び出しにO ( n )の作業と、サイズn /2のリストに対する2回の再帰呼び出しが含まれるため、再帰関係は次のようになります。

T（n）＝お（n）+2T（n2）。{\displaystyle T(n)=O(n)+2T\left({\frac {n}{2}}\right).}

分割統治法の再帰のマスター定理によれば、T ( n ) = O ( n log n )となります。

期待される時間計算量がO ( n log n )であることの正式な証明の概要は次のとおりです。重複は線形時間の前処理と後処理で処理できるか、分析したよりも簡単なケースと見なせるため、重複は存在しないものとします。入力がランダム順列の場合、ピボットのランクは 0 からn − 1までの一様ランダムです。その結果得られるパーティションの各部分のサイズはiとn − i − 1 になり、 i は 0 からn − 1までの一様ランダムです。したがって、すべての可能な分割を平均し、パーティションの比較回数がn − 1であることに注目すると、入力シーケンスのすべての順列の平均比較回数は、再帰関係を解くことで正確に推定できます。

C（n）＝n−1+1n∑私＝0n−1（C（私）+C（n−私−1））＝n−1+2n∑私＝0n−1C（私）{\displaystyle C(n)=n-1+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(ni-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)}
nC（n）＝n（n−1）+2∑私＝0n−1C（私）{\displaystyle nC(n)=n(n-1)+2\sum _{i=0}^{n-1}C(i)}
nC（n）−（n−1）C（n−1）＝n（n−1）−（n−1）（n−2）+2C（n−1）{\displaystyle nC(n)-(n-1)C(n-1)=n(n-1)-(n-1)(n-2)+2C(n-1)}
nC（n）＝（n+1）C（n−1）+2n−2{\displaystyle nC(n)=(n+1)C(n-1)+2n-2}
C（n）n+1＝C（n−1）n+2n+1−2n（n+1）≤C（n−1）n+2n+1＝C（n−2）n−1+2n−2（n−1）n+2n+1≤C（n−2）n−1+2n+2n+1  ⋮＝C（1）2+∑私＝2n2私+1≤2∑私＝1n−11私≈2∫1n1×d×＝2ln⁡n{\displaystyle {\begin{aligned}{\frac {C(n)}{n+1}}&={\frac {C(n-1)}{n}}+{\frac {2}{n+1}}-{\frac {2}{n(n+1)}}\leq {\frac {C(n-1)}{n}}+{\frac {2}{n+1}}\\&={\frac {C(n-2)}{n-1}}+{\frac {2}{n}}-{\frac {2}{(n-1)n}}+{\frac {2}{n+1}}\leq {\frac {C(n-2)}{n-1}}+{\frac {2}{n}}+{\frac {2}{n+1}}\\&\ \ \vdots \\&={\frac {C(1)}{2}}+\sum _{i=2}^{n}{\frac {2}{i+1}}\leq 2\sum _{i=1}^{n-1}{\frac {1}{i}}\approx 2\int _{1}^{n}{\frac {1}{x}}\mathrm {d} x=2\ln n\end{aligned}}}

再帰式を解くと、C ( n ) = 2 n ln n ≈ 1.39 n log 2 nとなります。

これは、平均するとクイックソートのパフォーマンスは最良の場合と比べて約39%しか低下しないことを意味します。この意味では、クイックソートは最悪の場合よりも最良の場合に近いと言えます。比較ソートでは、 n個の項目をソートするのに平均log 2 ( n !)回未満の比較しか使用できません（「比較ソート」の記事で説明されているように）。また、 nが大きい場合、スターリングの近似によりlog 2 ( n !) ≈ n (log 2 n − log 2 e )となるため、クイックソートは理想的な比較ソートと比べてそれほど劣ることはありません。この平均実行時間の短さは、クイックソートが他のソートアルゴリズムよりも実用的に優れているもう一つの理由です。

二分探索木の使用

以下の二分探索木(BST) は、クイックソートの各実行に対応しています。最初のピボットはルートノード、左半分のピボットは左サブツリーのルート、右半分のピボットは右サブツリーのルート、というように続きます。クイックソートの実行における比較回数は、挿入シーケンスによるBSTの構築中に行われる比較回数に等しくなります。したがって、ランダム化クイックソートの平均比較回数は、挿入された値がランダムな順列を形成する場合のBST構築の平均コストに等しくなります。 （×1、×2、…、×n）{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}

ランダムな順列を形成する値のシーケンスを挿入することで作成されたBSTを考えてみましょう。CをBSTの作成コストとします。 は、の挿入時にとの比較があったかどうかを表す2値ランダム変数です。 （×1、×2、…、×n）{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}C＝∑私∑j<私c私、j{\displaystyle C=\sum _{i}\sum _{j<i}c_{i,j}}c私、j{\displaystyle c_{i,j}}×私{\displaystyle x_{i}}×j{\displaystyle x_{j}}

期待値の線形性により、 Cの期待値は です。 E⁡[C]{\displaystyle \operatorname {E} [C]}E⁡[C]＝∑私∑j<私広報（c私、j）{\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})}

iとj < iを固定します。値をソートすると、j +1 個の区間が定義されます。構造上の重要な観察点は、アルゴリズムにおいてが と比較されるのは、が に隣接する2つの区間のいずれかに含まれる場合のみであるということです。 ×1、×2、…、×j{\displaystyle {x_{1},x_{2},\ldots,x_{j}}}×私{\displaystyle x_{i}}×j{\displaystyle x_{j}}×私{\displaystyle x_{i}}×j{\displaystyle x_{j}}

はランダムな順列なので、もランダムな順列であり、が に隣接する確率はちょうど であることに注目してください。 （×1、×2、…、×n）{\displaystyle (x_{1},x_{2},\ldots ,x_{n})}（×1、×2、…、×j、×私）{\displaystyle (x_{1},x_{2},\ldots ,x_{j},x_{i})}×私{\displaystyle x_{i}}×j{\displaystyle x_{j}}2j+1{\displaystyle {\frac {2}{j+1}}}

簡単に計算すると次のようになります。

E⁡[C]＝∑私∑j<私2j+1＝お（∑私ログ⁡私）＝お（nログ⁡n）。{\displaystyle \operatorname {E} [C]=\sum _{i}\sum _{j<i}{\frac {2}{j+1}}=O\left(\sum _{i}\log i\right)=O(n\log n).}

空間複雑性

クイックソートで使用されるスペースは、使用されるバージョンによって異なります。

クイックソートのインプレースバージョンは、以下の戦略を使用して慎重に実装すると、最悪の場合でも 空間計算量はO (log n )になります。

  • インプレースパーティショニングが使用されます。この不安定なパーティションにはO (1)のスペースが必要です。
  • 分割後、要素数が最も少ないパーティションが最初に（再帰的に）ソートされます。このソートに必要なスペースは最大でもO (log n )です。次に、もう一方のパーティションが末尾再帰または反復処理を用いてソートされます。この処理はコールスタックを増加させません。この考え方は、前述のようにR. Sedgewickによって提唱され、スタックの深さをO (log n )に制限します。[ 17 ] [ 20 ]

インプレース分割と不安定分割を用いたクイックソートは、再帰呼び出しを行う前に定数分のスペースのみを追加します。クイックソートは、ネストされた再帰呼び出しごとに一定量の情報を保存する必要があります。最良のケースでは最大でO (log n )回のネストされた再帰呼び出しが行われるため、O (log n )回のスペースを使用します。しかし、再帰呼び出しを制限するSedgewickのトリックがなければ、最悪のケースではクイックソートはO ( n )回のネストされた再帰呼び出しを行い、 O ( n )回の補助スペースを必要とする可能性があります。

ビット計算量の観点から見ると、loやhiなどの変数は定数領域を使用しません。n個の要素を持つリストのインデックスにはO(log n)ビットが必要です。このような変数はすべてのスタックフレームに存在するため、Sedgewickのトリックを用いたクイックソートではO ((log n ) 2 )ビットの領域が必要です。ただし、この領域要件はそれほど大きな問題ではありません。リストに異なる要素が含まれている場合、少なくともO ( nlog n )ビットの領域が 必要になるからです。

クイックソートのスタックフリー版も提案されている。これらは追加のスペース（より正確には、レコードを交換するためにソート対象レコードの型のセル1つと、インデックスとして使用される定数個の整数変数）を使用する。[ 28 ]お（1）{\displaystyle O(1)}

クイックソートのもう1つのバージョンは、あまり一般的ではないが、非インプレース版であり、作業領域としてO ( n )の空間を使用し、安定したソートを実装できる。作業領域により、入力配列を安定的に分割し、その後、入力配列にコピーして後続の再帰呼び出しに使用できる。Sedgewickの最適化は依然として適切である。

他のアルゴリズムとの関係

クイックソートは、二分木ソートのメモリ最適化版です。明示的な木構造に要素を順番に挿入するのではなく、クイックソートは、再帰呼び出しによって暗黙的に生成される木構造に要素を並列的に配置します。これらのアルゴリズムは全く同じ比較を行いますが、順序が異なります。ソートアルゴリズムにおいてしばしば望ましい特性として、安定性が挙げられます。つまり、等しい要素の順序は変更されないため、複数キーのテーブル（ディレクトリやフォルダの一覧など）の順序を自然な方法で制御できます。この特性は、インプレース・クイックソート（ポインタとバッファに一定の追加領域を使用し、明示的または暗黙的な再帰の管理にO (log n )の追加領域のみを使用する）では維持が困難です。ポインタ（リストや木構造など）やファイル（実質的にはリスト）を用いた表現のためにメモリが余分に使用されるバリアント・クイックソートでは、安定性を維持するのは簡単です。より複雑な、あるいはディスクバウンドなデータ構造は、一般的に仮想メモリやディスクの使用を増加させ、時間コストを増加させる傾向があります。

クイックソートの最も直接的な競合相手はヒープソートである。ヒープソートは単純さや、最悪でも実行時間がO ( n log n )と短いなどの利点があるが、ヒープソートの平均実行時間は、主に参照の局所性が悪いために、インプレース・クイックソートよりも遅いとされることが多い。[ 29 ]この結果は議論の余地があり、反対の見解を示す文献もある。[ 30 ] [ 31 ]クイックソートの主な欠点は、不適切なピボット選択を回避するために必要な実装の複雑さと、その結果O ( n 2 ) のパフォーマンスである。 イントロソートはクイックソートの変種であり、不適切なケースが検出されるとヒープソートに切り替えることでこの問題を解決します。C++（GNUおよびLLVM実装）などの主要なプログラミング言語はイントロソートを使用している。[ 32 ]

クイックソートは、別のO ( nlogn )ソートアルゴリズムであるマージソートとも競合します。マージソートの主な利点は、安定したソートであり、最悪ケースのパフォーマンスに優れていることです。マージソートの主な欠点は、アウトオブプレースアルゴリズムであるため、配列を操作する際に効率的な実装にはO ( n )の補助領域が必要になることです（インプレースパーティショニングと末尾再帰を使用したクイックソートではO (logn )、ヒープソートでは O (1)です）。

マージソートはリンクリスト上で非常に効果的に機能し、少量かつ一定量の補助記憶装置しか必要としません。リンクリストを用いた安定したソートとしてクイックソートを実装することも可能ですが、そうする理由はありません。クイックソートはランダムアクセスがないため、ピボット選択が適切でないことが多く、本質的にマージソートよりも劣るからです。マージソートは、ディスクストレージやネットワーク接続ストレージなどのアクセスが遅いメディアに保存された非常に大規模なデータセットの外部ソートにも最適なアルゴリズムです。

2 つのバケットを使用したバケット ソートはクイックソートと非常によく似ています。この場合のピボットは実質的に値の範囲の中央の値であり、均一に分散された入力に対して平均的に良好なパフォーマンスを発揮します。

選択ベースのピボット

選択アルゴリズムは、数値リストからk番目に小さいものを選択します。これは一般にソートよりも簡単な問題です。シンプルですが効果的な選択アルゴリズムの一つは、クイックソートとほぼ同じように動作するため、クイックセレクトと呼ばれます。違いは、両方のサブリストに対して再帰呼び出しを行うのではなく、目的の要素を含むサブリストに対して単一の末尾再帰呼び出しのみを行うことです。この変更により、平均計算量は線形時間、つまりO ( n )時間に低下し、選択には最適ですが、最悪の場合でも 選択アルゴリズムは依然としてO ( n 2 )です。

クイックセレクトの派生形である中央値の中央値アルゴリズムは、ピボットをより慎重に選択し、ピボットがデータの中央付近（30パーセンタイルと70パーセンタイルの間）に位置するようにすることで、線形時間（O ( n )）を保証します。この同じピボット戦略を用いて、クイックソートの派生形（中央値の中央値クイックソート）をO(nlogn )時間で構築できます。しかし、ピボット選択のオーバーヘッドが大きいため、実際にはあまり使用されません。

より抽象的に言えば、O ( n )選択アルゴリズムが与えられた場合、それを用いてクイックソートの各ステップで理想的なピボット（中央値）を見つけ、実行時間がO ( nlogn )のソートアルゴリズムを生成することができます。この変種の実装は平均してかなり遅くなりますが、最適な選択アルゴリズムが最適なソートアルゴリズムを生み出す可能性があることを示しているため、理論的には興味深いものです。

変種

マルチピボットクイックソート

単一のピボットを使用して2つのサブ配列に分割する代わりに、マルチピボットクイックソート（マルチクイックソートとも呼ばれる[ 21 ] ）は、 s − 1個のピボットを使用して入力をs個のサブ配列に分割します。デュアルピボットの場合（s = 3）は1970年代半ばにすでにセジウィックらによって検討されていましたが、結果として得られたアルゴリズムは実際には「古典的な」クイックソートよりも高速ではありませんでした。[ 33 ] 1999年に行われた、プロセッサキャッシュを効率的に使用するように調整された可変数のピボットを持つマルチクイックソートの評価では、命令数が約20％増加することがわかりましたが、シミュレーション結果から、非常に大きな入力に対してはより効率的であることが示唆されました。[ 21 ] 2009年にヤロスラフスキーが開発したデュアルピボットクイックソートのバージョン[ 34 ]は、プリミティブ配列をソートする標準アルゴリズムとしてJava 7に実装するのに十分なほど高速であることが判明しました（オブジェクトの配列のソートはTimsortを使用して行われます）。[ 36 ]このアルゴリズムのパフォーマンス上の利点は、主にキャッシュパフォーマンスに関連していることが判明し、[ 37 ]実験結果では、3ピボットバリアントは最新のマシンでさらに優れたパフォーマンスを発揮する可能性があることが示されています。[ 38 ] [ 39 ]

外部クイックソート

ディスク ファイルの場合、クイックソートに似たパーティション分割に基づく外部ソートが可能です。これは外部マージ ソートよりも低速ですが、余分なディスク領域を必要としません。 4 つのバッファーが使用されます (2 つは入力用、2 つは出力用)。ファイル内のレコード数、バッファーあたりのレコード数、ファイル内のバッファー セグメント数とします。データはファイルの両端から内側に向​​かって読み取られ (書き込まれ) ます。 はファイルの先頭から始まるセグメントを表し、 はファイルの末尾から始まるセグメントを表します。データは読み取りバッファーと読み取りバッファーに読み取られます。ピボット レコードが選択され、ピボット レコード以外のバッファーとバッファー内のレコードはピボット レコードとの比較に基づいて昇順で書き込みバッファーにコピーされ、降順で書き込みバッファーにコピーされます。いずれかのバッファーまたはバッファーがいっぱいになると、ファイルに書き込まれ、次のバッファーまたはバッファーがファイルから読み取られます。このプロセスは、すべてのセグメントが読み取られ、1 つの書き込みバッファーが残るまで続行されます。そのバッファーが書き込みバッファーの場合、ピボット レコードがそのバッファーに追加され、バッファーが書き込まれます。そのバッファが書き込みバッファの場合、ピボットレコードがバッファの先頭に追加され、バッファに書き込まれます。これはファイルの1つのパーティションステップを構成し、ファイルは2つのサブファイルで構成されます。各サブファイルの開始位置と終了位置は、再帰によってスタンドアロンスタックまたはメインスタックにプッシュ/ポップされます。スタックスペースを に制限するために、小さい方のサブファイルが最初に処理されます。スタンドアロンスタックの場合、大きい方のサブファイルパラメータをスタックにプッシュし、小さい方のサブファイルに対して反復処理を行います。再帰の場合は、まず小さい方のサブファイルに対して再帰処理を行い、次に大きい方のサブファイルを処理するために反復処理を行います。サブファイルが4 Bレコード以下になると、サブファイルはクイックソートによってインプレースソートされ、書き込まれます。これで、そのサブファイルはソートされ、ファイル内にインプレースで配置されます。この処理は、すべてのサブファイルがソートされ、インプレースで配置されるまで続けられます。ファイルの平均パス数は約 ですが、最悪のケースでは回のパスとなります（最悪のケースの内部ソートでは 回のパスに相当します）。[ 40 ]北＝{\displaystyle N=}B＝{\displaystyle B=}M＝北/B＝{\displaystyle M=N/B=}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}はい{\displaystyle Y}X{\displaystyle X}X{\displaystyle X}はい{\displaystyle Y}はい{\displaystyle Y}はい{\displaystyle Y}お（ログ2⁡（n））{\displaystyle O(\log _{2}(n))}1+ln⁡（北+1）（4B）{\displaystyle {\frac {1+\ln(N+1)}{(4B)}}}N{\displaystyle N}O(n2){\displaystyle O(n^{2})}

3元基数クイックソート

このアルゴリズムは、基数ソートとクイックソートを組み合わせたものです。配列（ピボット）から要素を1つ選び、文字列（マルチキー）の最初の文字（キー）を考慮します。残りの要素を、対応する文字がピボットの文字より小さい、等しい、大きいという3つの集合に分割します。「小さい」と「大きい」のパーティションを同じ文字で再帰ソートします。「等しい」のパーティションを次の文字（キー）で再帰ソートします。長さWビットのバイトまたはワードを使用してソートする場合、最良のケースはO ( KN ) 、最悪のケースはO (2 K N )、または少なくとも標準的なクイックソートと同様にO ( N 2 )（一意のキーN <2 Kの場合）です。Kは、クイックソートを含むすべての標準的な比較ソートアルゴリズムにおける隠れた定数です。これは一種の3方向クイックソートであり、中央のパーティションは、ピボットと 完全に等しい要素の（自明に）ソートされた部分配列を表します。

クイック基数ソート

Powers 氏によってO ( K )並列PRAMアルゴリズムとしても開発されました。これも基数ソートとクイックソートの組み合わせですが、クイックソートの左/右パーティションの決定はキーの連続するビットに基づいて行われるため、N KビットのキーではO ( KN )になります。すべての比較ソートアルゴリズムは暗黙的に、 KがΘ (log N )のトランス二分モデルを想定しています。つまり、Kが小さい場合はハッシュ テーブルまたは整数ソートを使用してO ( N )時間でソートできます。K ≫ log Nであっても要素がO (log N )ビット以内で一意である場合、残りのビットはクイックソートまたはクイック基数ソートのいずれによっても参照されません。それができない場合、すべての比較ソートアルゴリズムは、比較的役に立たないO ( K )ビットを調べるという同じオーバーヘッドを持つことになるが、クイック基数ソートは、標準的なクイックソートや基数クイックソートの最悪のケースであるO ( N2 )の動作を回避し、 uniqueprefix( K )≫logNという条件下では、これらの比較アルゴリズムの最良のケースでもより高速になる。比較ソート、基数ソート、並列ソートにおける隠れたオーバーヘッドに関する詳細な議論については、 Powers [ 41 ]を参照のこと。

ブロッククイックソート

比較に基づくソートアルゴリズムでは、比較回数を最小限に抑えるには、各比較から得られる情報の量を最大化する必要があり、比較結果は予測不可能であることを意味します。これにより、頻繁に分岐予測ミスが発生し、パフォーマンスが制限されます。[ 42 ] BlockQuicksort [ 43 ]は、クイックソートの計算を再配置して、予測不可能な分岐をデータ依存関係に変換します。分割時​​に、入力は中程度のサイズのブロック（データキャッシュに簡単に収まる）に分割され、2つの配列がスワップする要素の位置で埋められます。（条件分岐を回避するために、位置は無条件に配列の最後に格納され、スワップが必要な場合は末尾のインデックスがインクリメントされます。）2回目のパスでは、配列で示された位置の要素を交換します。両方のループには、通常は実行される終了テストという条件分岐が1つだけあります。

BlockQuicksort技術はLLVMのC++ STL実装libcxxに組み込まれており、ランダム整数シーケンスの性能を50%向上させます。introsortの一種であるパターンディフィート・クイックソート（pdqsort）にもこの技術が組み込まれています。[ 32 ]

部分クイックソートと増分クイックソート

クイックソートには、 k 個の最小または最大の要素を残りの入力から 分離するバリエーションがいくつかあります。

一般化

リチャード・コールとデイビッド・C・カンダシルは2004年、パーティションソートと呼ばれる1パラメータのソートアルゴリズム群を発見した。このアルゴリズムは平均すると（すべての入力順序が等確率である場合）、最大で（情報理論の下限に近い）比較と演算を実行し、最悪の場合でも比較（および演算）を実行する。これらはインプレースで実行され、追加のスペースのみを必要とする。実用的な効率と性能のばらつきの少なさは、セジウィックとベントレー・マキロイによる最適化されたクイックソートと比較して実証されている。[ 44 ]nlog⁡n+O(n){\displaystyle n\log n+{O}(n)}Θ(nlog⁡n){\displaystyle {\Theta }(n\log n)}Θ(nlog2⁡n){\displaystyle {\Theta }(n\log ^{2}n)}O(log⁡n){\displaystyle {O}(\log n)}

参照

注記

  1. ^ 「Sir Antony Hoare」 . コンピュータ歴史博物館. 2015年4月3日時点のオリジナルよりアーカイブ。 2015年4月22日閲覧。
  2. ^ a b Hoare, CAR (1961). 「アルゴリズム64：クイックソート」. Comm. ACM . 4 (7): 321. doi : 10.1145/366622.366644 .
  3. ^スキエナ、スティーブン・S. (2008). 『アルゴリズム設計マニュアル』 シュプリンガー. p. 129. ISBN 978-1-84800-069-8。
  4. ^ CL Foster,アルゴリズム、抽象化、実装、1992年、 ISBN 0122626605、98ページ
  5. ^ Shustek, L. (2009). 「インタビュー：CAR Hoare とのインタビュー」. Comm. ACM . 52 (3): 38– 41. doi : 10.1145/1467247.1467261 . S2CID 1868477 . 
  6. ^ 「クイックソートの発明者、トニー・ホーア卿とのクイックショートインタビュー」マルセロ・M・デ・バロス、2015年3月15日。
  7. ^ a b c d e f g Bentley, Jon L.; McIlroy, M. Douglas (1993). 「ソート関数のエンジニアリング」 .ソフトウェア：実践と経験. 23 (11): 1249– 1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105 . S2CID 8822797 .  
  8. ^ Van Emden, MH (1970年11月1日). 「アルゴリズム402：クイックソートの効率向上」 . Commun. ACM . 13 (11): 693– 694. doi : 10.1145/362790.362803 . ISSN 0001-0782 . S2CID 4774719 .  
  9. ^ベントレー、ジョン(2007). 「私が書いた中で最も美しいコード」. オラム、アンディ、ウィルソン、グレッグ (編著). 『美しいコード：一流プログラマーの思考法』. オライリーメディア. p. 30. ISBN 978-0-596-51004-6。
  10. ^ a b c「クイックソート分割：Hoare vs. Lomuto」 . cs.stackexchange.com . 2015年8月3日閲覧。
  11. ^ McIlroy, MD (1999年4月10日). 「クイックソートのキラーな敵」(PDF) .ソフトウェア：実践と経験. 29 (4): 341– 344. doi : 10.1002/(SICI)1097-024X(19990410)29:4<341::AID-SPE237>3.0.CO;2-R . S2CID 35935409 . 
  12. ^ a b Jon Bentley (1999). 『プログラミングの秘訣』 . Addison-Wesley Professional.
  13. ^ a b c dコーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009) [1990]. 「クイックソート」.アルゴリズム入門（第3版）. MIT Press and McGraw-Hill. pp.  170– 190. ISBN 0-262-03384-4。
  14. ^ワイルド、セバスチャン (2012). Java 7 のデュアル ピボット クイックソート(論文)。カイザースラウテルン工科大学。
  15. ^ Hoare, CAR (1962年1月1日). 「クイックソート」 .コンピュータジャーナル. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10 . ISSN 0010-4620 . 
  16. ^チャンドラムーリ、バドリッシュ、ゴールドスタイン、ジョナサン（2014年6月18日）「忍耐は美徳である」。2014 ACM SIGMOD国際データ管理会議議事録。Sigmod '14。ユタ州スノーバード、米国：ACM。pp.  731– 742。doi：10.1145 /2588555.2593662。ISBN 978-1-4503-2376-5. S2CID  7830071 .
  17. ^ a bセジウィック, ロバート(1998年9月1日). C言語アルゴリズム: 基礎、データ構造、ソート、検索、パート1～4 (第3版). ピアソン・エデュケーション. ISBN 978-81-317-1291-7。
  18. ^ GNU libcのqsort.c: [1] , [2]
  19. ^ http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html
  20. ^ a b Sedgewick, R. (1978). 「クイックソートプログラムの実装」. Comm. ACM . 21 (10): 847– 857. doi : 10.1145/359619.359631 . S2CID 10020756 . 
  21. ^ a b c LaMarca, Anthony; Ladner, Richard E. (1999). 「キャッシュがソートのパフォーマンスに与える影響」. Journal of Algorithms . 31 (1): 66– 104. CiteSeerX 10.1.1.27.1788 . doi : 10.1006/jagm.1998.0985 . S2CID 206567217 .小さなサブ配列を最後まで保存することは、命令数の観点からは理にかなっていますが、キャッシュのパフォーマンスの観点からは、全く間違ったやり方です。  
  22. ^ Umut A. Acar、Guy E Blelloch、Margaret Reid-Miller、Kanat Tangwongsan、「クイックソートとソートの下限値」、「並列および順次データ構造とアルゴリズム」。2013年。
  23. ^ Breshears, Clay (2012). 「プレフィックススキャンによるクイックソートパーティション」 . Dr. Dobb's .
  24. ^ミラー、ラス、ボクサー、ローレンス (2000).アルゴリズムの逐次的および並列的：統一的アプローチ. プレンティス・ホール. ISBN 978-0-13-086373-7。
  25. ^ Powers, David MW (1991).最適なスピードアップを実現する並列化クイックソートとラジックスソート. Proc. Int'l Conf. on Parallel Computing Technologies. CiteSeerX 10.1.1.57.9071 . 
  26. ^もう 1 つは、ピボットが Hoare の分割ルーチンのようにサブパーティションの 1 つに含まれているか、Lomuto のルーチンのようにサブパーティションの両方から除外されているかに応じて、 1つの要素を持つか、空 (要素が 0 個) になります。
  27. ^モトワニ、ラジーヴ、ラガヴァン、プラバカール（1995年8月25日）『ランダム化アルゴリズム』ケンブリッジ大学出版局、ISBN 9780521474658。
  28. ^ Ďurian, Branislav. 「スタックなしのクイックソート」. Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium . MFCS 1986. ブラティスラバ、チェコスロバキア: Springer Berlin Heidelberg.
  29. ^ Edelkamp, Stefan; Weiß, Armin (2019年1月7～8日). QuickMergesortによる最悪ケースの効率的ソート. ALENEX 2019: 第21回アルゴリズム工学と実験ワークショップ. サンディエゴ. arXiv : 1811.99833 . doi : 10.1137/1.9781611975499.1 . ISBN 978-1-61197-549-9.小さなインスタンスでは、ヒープソートはクイックソートよりもすでにかなり遅く (実験ではn = 2 10で 30% 以上)、大きなインスタンスではキャッシュ動作が貧弱です (実験では 2 28要素のソートでクイックソートより 8 倍以上遅い)。
  30. ^ Hsieh, Paul (2004). 「ソートの再考」 azillionmonkeys.com.
  31. ^ MacKay, David (2005年12月). 「ヒープソート、クイックソート、そしてエントロピー」 . 2009年4月1日時点のオリジナルよりアーカイブ。
  32. ^ a b Kutenin, Danila (2022年4月20日). 「Googleのスケールとその先におけるstd::sortの変更」 . Experimental chill .
  33. ^ Wild, Sebastian; Nebel, Markus E. (2012). Java 7のデュアルピボットクイックソートの平均ケース分析. European Symposium on Algorithms. arXiv : 1310.7409 . Bibcode : 2013arXiv1310.7409W .
  34. ^ Yaroslavskiy, Vladimir (2009). 「Dual-Pivot Quicksort」（PDF） . 2015年10月2日時点のオリジナル（PDF）からのアーカイブ。
  35. ^ Wild, S.; Nebel, M.; Reitzig, R.; Laube, U. (2013年1月7日). MaLiJAnを用いたJava 7のデュアルピボットクイックソートのエンジニアリング. Proceedings. Society for Industrial and Applied Mathematics. pp.  55– 69. doi : 10.1137/1.9781611972931.5 . ISBN 978-1-61197-253-5。
  36. ^ 「配列」 . Java Platform SE 7. Oracle . 2014年9月4日閲覧。
  37. ^ Wild, Sebastian (2015年11月3日). 「なぜデュアルピボットクイックソートは高速なのか？」arXiv : 1511.01138 [ cs.DS ].
  38. ^ Kushagra, Shrinu; López-Ortiz, Alejandro; Qiao, Aurick; Munro, J. Ian (2014).マルチピボットクイックソート：理論と実験. アルゴリズムエンジニアリングと実験に関するワークショップ (ALENEX) 論文集. doi : 10.1137/1.9781611973198.6 .
  39. ^クシャグラ、シュリヌ;ロペス・オルティス、アレハンドロ。マンロー、J.イアン;チャオ、オーリック（2014 年 2 月 7 日）。マルチピボット クイックソート: 理論と実験(PDF) (セミナー プレゼンテーション)。オンタリオ州ウォータールー。
  40. ^ Motzkin, D.; Hansen, CL (1982)、「最小限のスペース要件で効率的な外部ソート」、International Journal of Computer and Information Sciences、11 (6): 381– 396、doi : 10.1007/BF00996816、S2CID 6829805 
  41. ^ David MW Powers、「Parallel Unification: Practical Complexity」、オーストラレーシアコンピュータアーキテクチャワークショップ、フリンダース大学、1995年1月
  42. ^ Kaligosi, Kanela; Sanders, Peter (2006年9月11～13日).分岐予測ミスがクイックソートに与える影響(PDF) . ESA 2006: 第14回ヨーロッパアルゴリズムシンポジウム.チューリッヒ. doi : 10.1007/11841036_69 .
  43. ^エーデルカンプ、ステファン;ヴァイス、アルミン（2016年4月22日）。 「BlockQuicksort: 分岐の予測ミスがクイックソートに影響しない仕組み」。arXiv : 1604.06697 [ cs.DS ]。
  44. ^ Richard Cole, David C. Kandathil：「パーティションソートの平均ケース分析」、European Symposium on Algorithms、2004年9月14～17日、ノルウェー、ベルゲン。掲載： Lecture Notes in Computer Science 3221、Springer Verlag、pp. 240～251。

参考文献

Wikibookアルゴリズム実装には、クイックソートに関するページがあります。
「 https://en.wikipedia.org/w/index.php?title=Quicksort&oldid=1335343764#Variants」から取得