クイックソート

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

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

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

クイックソートの数学的分析によると、平均して、このアルゴリズムはを実行します。 $O(n\log {n})$ n個のアイテムをソートするための比較。最悪の場合、 $O(n^{2})$ 比較。

歴史

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

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

1975 年のRobert Sedgewickの博士論文は、クイックソートの研究における画期的な論文とみなされており、Samplesort、Van Emden による適応型パーティショニング^{[ 9 ]}などのさまざまなピボット選択スキームの分析に関連する多くの未解決問題を解決し、比較と交換の期待値の導出も行いました。^{[ 8 ]} 1993 年にJon BentleyとDoug McIlroy は、プログラミングライブラリで使用するためにさまざまな改良を加えました。これには、等しい要素を処理する手法や、9 つの要素のサンプルを 3 つのグループに分割し、3 つのグループの 3 つの中央値の中央値を選択する擬似中央値 9と呼ばれるピボットスキームが含まれます。 ^{[ 8 ]} Bentley は、 Nico Lomutoによるものとされる、より単純でコンパクトな別のパーティショニングスキームを著書Programming Pearlsで説明しました。後に Bentley は、Hoare のバージョンを何年も使用していたが、実際には理解していなかったが、Lomuto のバージョンは正しいことを証明できるほど単純だったと書いています。^[¹⁰^]ベントレーは、同じエッセイの中でクイックソートを「私がこれまでに書いた中で最も美しいコード」と評した。ロムートの分割方式も教科書『アルゴリズム入門』で普及したが、平均して3倍のスワップを行い、すべての要素が等しい場合は実行時間が $O$ $($ $n$ $2$ $)$ に低下するため、ホアの方式より劣る。^[¹¹^]マキルロイは1998年にさらにアンチクイックソート( aqsort )関数を作成し、その場で敵対的データを生成することで、1993年のクイックソートの変種でさえも常に2次的な動作に追い込んだ。^[¹²^]

アルゴリズム

ランダムな数値セットに対するクイックソートの完全な例。網掛けされた要素はピボットです。これは常にパーティションの最後の要素として選択されます。ただし、このように常にパーティションの最後の要素をピボットとして選択すると、*既にソートされた*配列や同一要素の配列ではパフォーマンスが低下します ( $O (n 2)$ ) 。ソート済み/同一要素のサブ配列は、大きなセットのソート手順の終盤に多く出現するため、ピボットを中央の要素として選択するクイックソートアルゴリズムのバージョンは、この図で説明されているアルゴリズムよりも大きな数値セットでずっと高速に実行されます。

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

範囲内の要素が2つ未満の場合は、何もすることがないので直ちに処理を終了します。
（オプション）範囲が非常に短い場合は、専用のソート方法を使用して結果を返します。たとえば、2つの要素の範囲は、1回の比較でソートできます。
それ以外の場合は、範囲内の値（ピボットと呼ばれる）を選択します。（ピボットの選択方法はパフォーマンスに大きく影響しますが、正確性には影響しません。）
範囲を分割します。要素をサブ範囲に並べ替え、ピボットより小さい値を持つすべての要素を最初のサブ範囲に、ピボットより大きい値を持つすべての要素を2番目のサブ範囲に配置します。ピボットと等しい値を持つ要素は、どちらかのサブ範囲、または2つのサブ範囲の間に3番目のサブ範囲を配置できます。この中間のサブ範囲は省略可能ですが、クイックソートでは最初の2つのサブ範囲がそれぞれ元の範囲より厳密に小さい必要があり、これは少なくとも1つのピボット要素を中間に配置することで最も簡単に実現できます。
既に最終位置にある中央のサブレンジを除き、2つのサブレンジに対してクイックソートを再帰的に適用します。

これらは、正しく動作するための基本的な要件です。上記で指定されていない詳細、特に分割アルゴリズム、中でもピボットの選択方法は、入力配列によってはアルゴリズムのパフォーマンスに大きな影響を与える可能性があります。したがって、クイックソートの効率について議論するには、まずこれらの選択肢を明確にする必要があります。ここでは、2つの具体的な分割方法について説明します。

ロムート分割スキーム

この方式は Nico Lomuto によるもので、Bentley が著書Programming Pearls ^{[ 13 ]}で、また Cormen らが著書Introduction to Algorithms ^{[ 14 ]}で普及させた。ほとんどの定式化では、この方式は配列の最後の要素をピボットとして選択する。アルゴリズムは、別のインデックスjを使用して配列をスキャンしながらインデックスiを維持し、 loからi-1 (両端を含む)までの要素がピボットより小さく、iからj (両端を含む) までの要素がピボット以上となるようにする。この方式はより簡潔で理解しやすいため、入門教材でよく使用されるが、すべての要素が等しい場合など、Hoare の元の方式よりも効率が悪い。^[¹⁵^]この方式による Quicksort の複雑さは、配列が既に順序付けられている場合、分割が最悪の分割となるため $O$ $($ $n$ $2$ $)に低下する。$ ^[¹¹^]パフォーマンスを向上させるために、ピボットの選択方法、等しい要素の処理方法、小さな配列に対する挿入ソートなどの他のソートアルゴリズムの使用など、さまざまなバリアントが提案されています。擬似コードでは、配列 $Aの$ loからhi (両端を含む) の要素をソートするクイックソートは次のように表現できます。^[¹⁴^]

// 配列の一部をソートし、それをパーティションに分割してから、それらのパーティションをソートするアルゴリズムquicksort(A, lo, hi)は// インデックスが正しい順序になっていることを確認するif lo >= hi || lo < 0 then 戻る // 配列を分割し、ピボットインデックスを取得する p := partition(A, lo, hi) // 2つのパーティションをソートする quicksort(A, lo, p - 1) // ピボットの左側 quicksort(A, p + 1, hi) // ピボットの右側// 配列を2つのパーティションに分割するアルゴリズムpartition(A, lo, hi) is pivot := A[hi] // 最後の要素をピボットとして選択する// 一時的なピボットインデックス i := 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)を使用します。

ホアのパーティション計画

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

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

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

擬似コードでは、^{[ 14 ]}

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

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

Hoare の方式は、平均して交換回数が 3 分の 1 であるため、Lomuto の分割方式よりも効率的です。また、前述のように、すべての値が等しい場合でも、提示された実装はバランスの取れたパーティションを作成します。^{[ 11 ]}これは 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 )を返すか、および分割関数でピボットをどのように選択するか(床関数か天井関数か)によって決まります。

まず、 (lo..p)と(p+1..hi)の再帰の選択について、複数の同一要素が存在する配列[0, 0] をソートする例で検討します。分割関数でインデックスが交差した後にインデックス 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 (インデックスが交差した後の「後」のインデックス) を返す必要があり、「天井値」をピボットとして選択する必要があります。この 2 つのニュアンスは、それぞれ複数の同一要素が存在する配列 ( [0, 0] ) と既にソートされた配列[0, 1]のソートの例を考えると、再び明確になります。このバージョンの再帰では、同じ理由で、最初の要素をピボットとして選択することは避ける必要があることに注意してください。

実装上の問題

ピボットの選択

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

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

mid := ⌊(lo + hi) / 2⌋ if 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 つの中央値ピボットを使用すると、スワップの期待値が 3% 増加する代わりに、この値は $C$ $n$ $, 2$ $\approx 1.188$ $n$ $log$ $nに減少します。$ ^[⁸^]より大きな配列の場合、さらに強力なピボット規則は、9 番目の要素を選択する再帰的中央値 3 (Mo3) であり、次のように定義されます^[⁸^{] 。}

ninther(a) = median(Mo3(a の 最初 の 1/3) , Mo3 (a の 中央 1/3), Mo3 ( a の 最後 の 1/3))

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

繰り返し要素

前述のLomuto分割方式のような分割アルゴリズム（適切なピボット値を選択するものであっても）では、繰り返し要素が多い入力に対してクイックソートのパフォーマンスが低下します。この問題は、入力要素がすべて等しい場合に顕著になります。各再帰において、左側のパーティションは空になり（入力値にピボット値より小さい値はありません）、右側のパーティションは要素が1つ減っただけです（ピボット値が削除されます）。その結果、Lomuto分割方式では、等しい値の配列をソートするのに2乗時間かかります。しかし、Hoare分割方式のような分割アルゴリズムでは、繰り返し要素があると一般的に分割効率が向上し、ピボット値と等しい要素の不要なスワップが発生する可能性はあるものの、繰り返し要素の数が増えるにつれて実行時間は一般的に短くなります（メモリキャッシュによってスワップのオーバーヘッドが削減されるため）。すべての要素が等しい場合、Hoare分割方式では要素が不要なスワップされますが、上記のHoare分割の項で述べたように、分割自体は最良のケースとなります。

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

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

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

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

最適化

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

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

並列化

クイックソートの分割統治方式は、タスク並列処理による並列化に適しています。分割ステップは、並列プレフィックス和アルゴリズムを使用して、分割された配列の各セクションのインデックスを計算することによって実行されます。^[²³^]^[²⁴^] $サイズn$ の配列が与えられた場合、分割ステップは $O($ $n$ $)の作業を$ $O$ $(log$ $n$ $)$ 時間で実行し、 $O($ $n$ $) の$ 追加スクラッチ領域を必要とします。配列が分割された後、2 つのパーティションを再帰的に並列にソートできます。ピボットの理想的な選択を仮定すると、並列クイックソートは、 $O($ $n$ $log$ $n$ $)$ の作業を $O(log$ $2$ $n$ $)$ 時間で実行し、 $O($ $n$ $)の追加領域を使用して、サイズ$ $n$ の配列をソートします。

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

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

形式分析

最悪のシナリオ分析

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

これが各パーティションで繰り返し発生する場合、各再帰呼び出しは、前のリストよりサイズが 1 少ないリストを処理します。したがって、サイズ 1 のリストに到達するまでに $n - 1 回のネストされた呼び出しが必要になります。これは、$ 呼び出しツリーが $n - 1 回$ のネストされた呼び出しの線形チェーンであることを意味します。i $番目$ の呼び出しは、パーティションを実行するために $O (n - i)$ の作業を行い、 $\textstyle \sum _{i=0}^{n}(n-i)=O(n^{2})$ そのため、その場合はクイックソートは $O (n²)の時間$ で実行されます。

最良ケース分析

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

平均ケース分析

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

この主張を証明する一般的な方法として、パーセンタイル、漸化式、二分探索木を用いるものが3つあり、それぞれがクイックソートの動作原理について異なる洞察を与えてくれる。

パーセンタイルを使用する

各ピボットの順位が中央50%、つまり25パーセンタイルから75パーセンタイルの間にある場合、各要素は少なくとも25%、最大75%の割合で分割されます。このようなピボットを一貫して選択すれば、リストを分割する必要のある要素は最大でも $\log _{4/3}n$ サイズ1のリストに到達するまでに何回も実行され、 $O (n log n)の$ アルゴリズムが得られます。

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

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

反復法を用いる

$別の方法として、サイズn$ のリストをソートするのに必要な時間である $T$ $($ $n$ $)$ の係数に対する漸化式を立てる方法がある。最も不均衡なケースでは、1 回のクイックソート呼び出しに $O$ $($ $n$ $)の作業と、サイズ$ $0$ および $n$ $-1$ のリストに対する 2 つの再帰呼び出しが含まれるため、漸化式は次のようになる。

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)=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+{\frac {1}{n}}\sum _{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac {2}{n}}\sum _{i=0}^{n-1}C(i)

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)

nC(n)=(n+1)C(n-1)+2n-2

{\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 \approx 1.39 n log 2 n$ となる。

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

二分探索木を使用する

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

シーケンスの挿入によって作成されたBSTを考えてみましょう $(x_{1},x_{2},\ldots ,x_{n})$ ランダムな順列を形成する値の集合。C を $BST$ の作成コストとします。 $C=\sum _{i}\sum _{j<i}c_{i,j}$ 、どこ $c_{i,j}$ 挿入中に $x_{i}$ 比較対象があった $x_{j}$ 。

期待値の線形性により、期待値は $\operatorname {E} [C]$ $C$ の $\operatorname {E} [C]=\sum _{i}\sum _{j<i}\Pr(c_{i,j})$ 。

$i$ と $j < i$ を固定します。 ${x_{1},x_{2},\ldots ,x_{j}}$ ソートされたら、 $j +1 個$ の区間を定義します。コアとなる構造的観察は次のとおりです。 $x_{i}$ と比較される $x_{j}$ アルゴリズムにおいて、 $x_{i}$ に隣接する 2 つの区間のいずれかに収まる $x_{j}$ 。

なぜなら $(x_{1},x_{2},\ldots ,x_{n})$ ランダムな順列です。 $(x_{1},x_{2},\ldots ,x_{j},x_{i})$ もランダムな順列なので、 $x_{i}$ に隣接しています $x_{j}$ まさに ${\frac {2}{j+1}}$ 。

簡略化すると、次のようになります。

\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)$ に制限します。^{[ 18 ]}^{[ 21 ]}

インプレースかつ不安定なパーティショニングを用いたクイックソートは、再帰呼び出しを行う前に一定量の追加スペースのみを使用します。クイックソートは、ネストされた再帰呼び出しごとに一定量の情報を格納する必要があります。最良の場合、ネストされた再帰呼び出しは最大で $O (log n)回なので、使用するスペースは$ $O (log n)$ です。しかし、再帰呼び出しを制限するセジウィックのトリックがない場合、最悪の場合、クイックソートは $O (n)回のネストされた再帰呼び出しを行い、$ $O (n)$ の補助スペースを必要とする可能性があります。

ビット複雑度の観点から見ると、loやhiのような変数は定数空間を使用しません。n 個の項目を持つリストにインデックスを付けるには O (log n ) ビットが必要です $。$ この $ような変数は$ すべてのスタックフレームに存在するため、セジウィックのトリックを使用したクイックソートには $O$ $((log$ $n$ $)$ $2$ $)$ ビットの空間が必要です。ただし、リストに異なる要素が含まれていれば、少なくとも $O$ $($ $n$ $log$ $n$ $)$ ビットの空間が必要になるため、この空間要件はそれほどひどいものではありません。

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

もう一つの、あまり一般的ではない非インプレース型のクイックソートは、作業用ストレージに $O$ $($ $n$ $)$ の空間を使用し、安定ソートを実装できます。作業用ストレージにより、入力配列を安定的に分割し、後続の再帰呼び出しのために入力配列にコピーし直すことができます。セジウィックの最適化は依然として有効です。

他のアルゴリズムとの関連性

クイックソートは、バイナリツリーソートのスペース最適化バージョンです。明示的なツリーに項目を順次挿入する代わりに、クイックソートは再帰呼び出しによって暗示されるツリーに項目を並行して配置します。アルゴリズムは全く同じ比較を行いますが、順序が異なります。ソートアルゴリズムに求められる特性として、安定性があります。つまり、等しいと比較される要素の順序は変更されず、マルチキーテーブル（ディレクトリやフォルダのリストなど）の順序を自然な方法で制御できます。この特性は、インプレースクイックソート（ポインタとバッファに定数の追加スペース、明示的または暗黙的な再帰の管理に $O (log n)$ の追加スペースのみを使用する）では維持が困難です。ポインタ（リストやツリーなど）またはファイル（実質的にはリスト）を使用した表現による追加メモリを伴うバリアントクイックソートでは、安定性を維持するのは容易です。より複雑な、またはディスクバウンドなデータ構造は、一般的に仮想メモリまたはディスクの使用が増加するため、時間コストが増加する傾向があります。

クイックソートの最も直接的な競合はヒープソートです。ヒープソートは、シンプルさと最悪の場合の実行時間が $O (n log n)$ であるという利点がありますが、ヒープソートの平均実行時間は、参照の局所性が悪いため、通常、インプレースクイックソートよりも遅いと考えられています。^[³⁰^]この結果には議論の余地があり、反対の結果を示す論文もあります。^[³¹^]^[³²^]クイックソートの主な欠点は、悪いピボット選択を回避するために必要な実装の複雑さと、結果としての $O$ $($ $n$ $2$ $)$ のパフォーマンスです。イントロソートは、悪いケースが検出されたときにヒープソートに切り替えることでこの問題を解決するクイックソートの変種です。C++ (GNU および LLVM 実装) などの主要なプログラミング言語は、イントロソートを使用しています。^[³³^]

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

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

2つのバケットを使用するバケットソートはクイックソートと非常によく似ています。この場合、ピボットは実質的に値の範囲の中央の値であり、均一に分布した入力に対しては平均的に良好な結果をもたらします。

選択に基づくピボット

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

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

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

バリエーション

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

単一のピボットを使用して 2 つのサブ配列に分割する代わりに、マルチピボットクイックソート (マルチクイックソート^{[ 22 ]} $とも呼ばれる) は、 s$ $- 1 個$ のピボットを使用して入力を $s$ 個のサブ配列に分割します。デュアルピボット ( $s$ $= 3$ ) の場合については、1970 年代半ばに Sedgewick らが検討しましたが、結果として得られたアルゴリズムは、実際には「古典的な」クイックソートよりも高速ではありませんでした。^[³⁴^]プロセッサキャッシュを効率的に使用するために調整された可変数のピボットを持つマルチクイックソートの 1999 年の調査では、命令数が約 20% 増加することがわかりましたが、シミュレーション結果では、非常に大きな入力に対してはより効率的になることが示唆されました。^[²²^] 2009 年に Yaroslavskiy によって開発されたデュアルピボットクイックソートのバージョン^[³⁵^]は、 Java 7にプリミティブ配列をソートする標準アルゴリズムとして実装されるのに十分な速さであることが判明しました^[³⁶^] (オブジェクトの配列のソートは Timsortを使用して行われます)。^[³⁷^]このアルゴリズムのパフォーマンス上の利点は、その後、主にキャッシュのパフォーマンスに関連していることが判明し [ 38 ]、^実験^結果^によると、3 つのピボットのバリアントは最新のマシンでさらに優れたパフォーマンスを発揮する可能性があります。^[³⁹^]^[⁴⁰^]

外部クイックソート

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

3方向基数クイックソート

このアルゴリズムは、基数ソートとクイックソートを組み合わせたものです。配列から要素 (ピボット) を選択し、文字列 (マルチキー) の最初の文字 (キー) を考慮します。残りの要素を、対応する文字がピボットの文字より小さい、等しい、大きいの 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$ $($ $N$ $2$ $)の動作を回避し、$ $uniqueprefix($ $K$ $) ≫ log$ $N$ のこれらの条件下では、これらの比較アルゴリズムの最良のケースでも高速になります。比較、基数、および並列ソートの隠れたオーバーヘッドの詳細については、Powers ^[⁴²^{]を参照してください。}

ブロッククイックソート

比較ベースのソートアルゴリズムでは、比較回数を最小限に抑えるには、各比較から得られる情報量を最大化する必要があります。つまり、比較結果は予測不可能です。これにより、頻繁に分岐の誤予測が発生し、パフォーマンスが制限されます。^{[ 43 ]} BlockQuicksort ^{[ 44 ]}は、クイックソートの計算を再配置して、予測不可能な分岐をデータ依存性に変換します。パーティショニングでは、入力は中サイズのブロック（データキャッシュに容易に収まる）に分割され、2 つの配列に交換する要素の位置が格納されます。（条件分岐を回避するために、位置は無条件に配列の末尾に格納され、交換が必要な場合は末尾のインデックスがインクリメントされます。）2 回目のパスでは、配列で指定された位置の要素が交換されます。どちらのループにも、終了のテストという 1 つの条件分岐のみがあり、通常は実行されます。

BlockQuicksort の手法はLLVMの C++ STL 実装である libcxx に組み込まれており、ランダムな整数シーケンスに対して 50% の改善を実現しています。パターン回避クイックソート ( pdqsort ) は、イントロソートの一種で、この手法を採用しています。^{[ 33 ]}

部分的および増分クイックソート

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

一般化

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

注記

↑ 「サー・アントニー・ホア」。コンピュータ歴史博物館。2015年4月3日のオリジナルからアーカイブ済み。2015年4月22日取得。
↑ウィルソン、ジョン（2026年4月3日）。「ロバート・フォックス、メアリー・ランドMBE、サー・トニー・ホーア、ビルテ・ガルディカス」。『ラスト・ワード』、ラジオ4。英国：BBC 。 2026年4月4日取得。（番組開始から14分50秒、ビル・ロスコーへのインタビュー。）
1 2ホア、カリフォルニア州(1961)。「アルゴリズム 64: クイックソート」。通信ACM。4 (7): 321.土井: 10.1145/366622.366644。
↑スキエナ、スティーブン S. (2008).アルゴリズム設計マニュアル. Springer. p. 129. ISBN 978-1-84800-069-8。
↑ CL Foster、『アルゴリズム、抽象化、実装』、1992年、 ISBN 012262660598ページ
↑ Shustek, L. (2009). "インタビュー: CAR Hoare へのインタビュー". Comm. ACM . 52 (3): 38– 41. doi : 10.1145/1467247.1467261 . S2CID 1868477 .
↑ 「クイックソートの発明者、サー・トニー・ホーアへのクイックショートインタビュー」。マルセロ・M・デ・バロス。2015年3月15日。
1 2 3 4 5 6 7 Bentley, Jon L.; McIlroy, M. Douglas (1993). "ソート関数の設計" . Software: Practice and Experience . 23 (11): 1249– 1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105 . S2CID 8822797 .
↑ Van Emden, MH (1970年11月1日). "アルゴリズム402：クイックソートの効率向上" . Commun. ACM . 13 (11): 693–694 . doi : 10.1145/362790.362803 . ISSN 0001-0782 . S2CID 4774719 .
↑ベントレー、ジョン（2007）。「私が書いたことのない最も美しいコード」。オーラム、アンディ、ウィルソン、グレッグ（編）『美しいコード：一流プログラマーが語る思考法』。オライリー・メディア。30ページ。ISBN 978-0-596-51004-6。
1 2 3 「クイックソート分割：Hoare vs. Lomuto」 . cs.stackexchange.com . 2015年8月3日取得.
↑ McIlroy, MD (1999年4月10日). "クイックソートのキラー敵対者" (PDF) . Software: Practice and Experience . 29 (4): 341– 344. doi : 10.1002/(SICI)1097-024X(19990410)29:4 < 341::AID-SPE237 > 3.0.CO ; 2-R . S2CID 35935409 .
1 2ジョン・ベントレー (1999).プログラミングの真珠. アディソン・ウェスリー・プロフェッショナル。
1 2 3 4コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。「クイックソート」。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ページ170–190。ISBN 0-262-03384-4。
↑ワイルド、セバスチャン (2012)。Java 7 のデュアルピボットクイックソート(論文)。カイザースラウテルン工科大学。
↑ Hoare, CAR (1962年1月1日). "Quicksort" . The Computer Journal . 5 (1): 10– 16. doi : 10.1093/comjnl/5.1.10 . ISSN 0010-4620 .
↑ Chandramouli, Badrish; Goldstein, Jonathan (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 .
1 2セッジウィック、ロバート（1998年9月1日）。C言語によるアルゴリズム：基礎、データ構造、ソート、検索、パート1～4（第3版）。ピアソン・エデュケーション。ISBN 978-81-317-1291-7。
↑ GNU libcの qsort.c:、
↑ http://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html
1 2 Sedgewick, R. (1978). "クイックソートプログラムの実装". Comm. ACM . 21 (10): 847– 857. doi : 10.1145/359619.359631 . S2CID 10020756 .
1 2 3 LaMarca, Anthony; Ladner, Richard E. (1999). " The Influence of Caches on the Performance of Sorting". Journal of Algorithms . 31 (1): 66–104 . CiteSeerX 10.1.1.27.1788 . doi : 10.1006/jagm.1998.0985 . S2CID 206567217.小さなサブ配列を最後に保存することは命令数の観点からは理にかなっているが、キャッシュのパフォーマンスの観点からはまさに間違った行為である。
↑ Umut A. Acar、Guy E Blelloch、Margaret Reid-Miller、Kanat Tangwongsan、「クイックソートとソートの下限」、並列および逐次データ構造とアルゴリズム、2013年。
↑ Breshears, Clay (2012). "Quicksort Partition via Prefix Scan" . Dr. Dobb's .
↑ミラー、ラス；ボクサー、ローレンス（2000）。アルゴリズム逐次および並列：統一的アプローチ。プレンティスホール。ISBN 978-0-13-086373-7。
↑ Powers, David MW (1991).並列化されたクイックソートと基数ソートの最適な高速化. 並列コンピューティング技術に関する国際会議議事録. CiteSeerX 10.1.1.57.9071 .
↑もう一方の要素は、ピボットがHoareのパーティショニングルーチンのようにサブパーティションのいずれかに含まれているか $、Lomutoのルーチンのように両方から除外されているかに応じて、 1つ$ $の$ 要素を持つか、空（0個の要素を持つ）になるかのいずれかになります。
↑ Motwani, Rajeev; Raghavan, Prabhakar (1995年8月25日). Randomized Algorithms . Cambridge University Press. ISBN 9780521474658。
↑ Ďurian, Branislav. 「スタックなしのクイックソート」. Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium . MFCS 1986. Bratislava, Czechoslovakia: Springer Berlin Heidelberg.
↑ 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}²⁸要素のソートでクイックソートより8倍以上遅い）。
↑ Hsieh, Paul (2004). "Sorting revisited" . azillionmonkeys.com.
↑ MacKay, David (2005 年 12 月). "ヒープソート、クイックソート、およびエントロピー" . 2009 年 4 月 1 日にオリジナルからアーカイブされました。
1 2 Kutenin, Danila (20 April 2022). "Google の規模とそれを超える規模での std::sort の変更" . Experimental chill .
↑ Wild, Sebastian; Nebel, Markus E. (2012). Java 7 のデュアルピボットクイックソートの平均ケース分析。欧州アルゴリズムシンポジウム。arXiv : 1310.7409。Bibcode : 2013arXiv1310.7409W。
↑ヤロスラフスキー、ウラジミール (2009)。「デュアルピボットクイックソート」(PDF)。 2015年10月2日にオリジナル(PDF)からアーカイブされました。
↑ 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。
↑ 「配列」 . Java Platform SE 7. Oracle . 2014年9月4日取得。
↑ Wild, Sebastian (2015年11月3日). "なぜデュアルピボットクイックソートは速いのか？". arXiv : 1511.01138 [ cs.DS ].
↑ Kushagra, Shrinu; López-Ortiz, Alejandro; Qiao, Aurick; Munro, J. Ian (2014). Multi-Pivot Quicksort: Theory and Experiments . Proc. Workshop on Algorithm Engineering and Experiments (ALENEX). doi : 10.1137/1.9781611973198.6 .
↑クシャグラ、シュリヌ。ロペス・オルティス、アレハンドロ。マンロー、J.イアン;チャオ、オーリック（2014 年 2 月 7 日）。マルチピボットクイックソート: 理論と実験(PDF) (セミナープレゼンテーション)。オンタリオ州ウォータールー。
↑ Motzkin, D.; Hansen, CL (1982), "最小限のスペース要件で効率的な外部ソート", International Journal of Computer and Information Sciences , 11 (6): 381–396 , doi : 10.1007/BF00996816 , S2CID 6829805
↑ David MW Powers、「並列統合：実践的な複雑性」、オーストラリア・アジアコンピュータアーキテクチャワークショップ、フリンダース大学、1995年1月
↑ Kaligosi, Kanela; Sanders, Peter (2006年9月11日～13日).分岐予測の誤りがクイックソートに与える影響(PDF) . ESA 2006: 第14回欧州アルゴリズムシンポジウム.チューリッヒ. doi : 10.1007/11841036_69 .
↑エーデルカンプ、ステファン。ヴァイス、アルミン（2016年4月22日）。「BlockQuicksort: 分岐の予測ミスがクイックソートに影響しない仕組み」。arXiv : 1604.06697 [ cs.DS ]。
↑ Richard Cole、David C. Kandathil:「パーティションソートの平均ケース分析」、欧州アルゴリズムシンポジウム、2004年9月14～17日、ノルウェー、ベルゲン。出版： Lecture Notes in Computer Science 3221、Springer Verlag、pp. 240–251。

参考文献

Sedgewick, R. (1978). "クイックソートプログラムの実装". Comm. ACM . 21 (10): 847–857 . doi : 10.1145/359619.359631 . S2CID 10020756 .
Dean, BC (2006). 「ランダム化された『分割統治』アルゴリズムの単純な期待実行時間解析」 . Discrete Applied Mathematics . 154 : 1– 5. doi : 10.1016/j.dam.2005.07.005 .
Hoare, CAR (1961). "アルゴリズム 63: 分割". Comm. ACM . 4 (7): 321. doi : 10.1145/366622.366642 . S2CID 52800011 .
Hoare, CAR (1961). "アルゴリズム 65: Find". Comm. ACM . 4 (7): 321–322 . doi : 10.1145/366622.366647 .
ホア、カリフォルニア州(1962)。「クイックソート」。計算します。 J. 5 (1): 10–16 . doi : 10.1093/comjnl/5.1.10。（ホアとジョーンズ編『計算機科学に関するエッセイ集』、1989年に再録。）
Musser, David R. (1997). "内省的ソートおよび選択アルゴリズム" . Software: Practice and Experience . 27 (8): 983– 993. doi : 10.1002/(SICI)1097-024X(199708)27:8 < 983::AID-SPE117 > 3.0.CO ; 2-# .
ドナルド・クヌース著『コンピュータプログラミングの技法』第3巻：ソートと検索、第3版。アディソン・ウェスリー、1997年。ISBN 0-201-89685-0セクション 5.2.2「交換によるソート」の 113～122 ページ。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。『アルゴリズム入門』第2版。MIT PressおよびMcGraw-Hill、2001年。ISBN 0-262-03293-7第7章：クイックソート、145～164ページ。
モラー、ファロン。「クイックソートの分析」（PDF）。2022年7月7日にオリジナル（PDF）からアーカイブ。2024年12月3日に取得。（CS 332：アルゴリズム設計。スウォンジー大学コンピュータサイエンス学部。）
Martínez, C.; Roura, S. (2001). "QuicksortとQuickselectにおける最適なサンプリング戦略". SIAM J. Comput. 31 (3): 683– 705. CiteSeerX 10.1.1.17.4954 . doi : 10.1137/S0097539700382108 .
Bentley, JL; McIlroy, MD ( 1993). "ソート関数の設計". Software: Practice and Experience . 23 (11): 1249–1265 . CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105 . S2CID 8822797 .

外部リンク

「アニメーションによるソートアルゴリズム：クイックソート」。 2015年3月2日にオリジナルからアーカイブ済み。2008年11月25日に取得。– グラフィックによるデモンストレーション
「アニメーションによるソートアルゴリズム：クイックソート（3分割）」。 2015年3月6日にオリジナルからアーカイブ済み。2008年11月25日に取得。
オープンデータ構造 – セクション 11.1.2 – クイックソート、パット・モリン
クイックソートのインタラクティブな図解とコード解説
Quicksort による高速ソート：初心者向けの徹底解説

[1] 「サー・アントニー・ホア」。コンピュータ歴史博物館。2015年4月3日のオリジナルからアーカイブ済み。2015年4月22日取得。

[bbc-2] ウィルソン、ジョン（2026年4月3日）。「ロバート・フォックス、メアリー・ランドMBE、サー・トニー・ホーア、ビルテ・ガルディカス」。『ラスト・ワード』、ラジオ4。英国：BBC 。 2026年4月4日取得。（番組開始から14分50秒、ビル・ロスコーへのインタビュー。）

[alg64-3] 1 2ホア、カリフォルニア州(1961)。「アルゴリズム 64: クイックソート」。通信ACM。4 (7): 321.土井: 10.1145/366622.366644。

[skiena-4] スキエナ、スティーブン S. (2008).アルゴリズム設計マニュアル. Springer. p. 129. ISBN 978-1-84800-069-8。

[5] CL Foster、『アルゴリズム、抽象化、実装』、1992年、 ISBN 012262660598ページ

[6] Shustek, L. (2009). "インタビュー: CAR Hoare へのインタビュー". Comm. ACM . 52 (3): 38– 41. doi : 10.1145/1467247.1467261 . S2CID 1868477 .

[7] 「クイックソートの発明者、サー・トニー・ホーアへのクイックショートインタビュー」。マルセロ・M・デ・バロス。2015年3月15日。

[engineering-8] 1 2 3 4 5 6 7 Bentley, Jon L.; McIlroy, M. Douglas (1993). "ソート関数の設計" . Software: Practice and Experience . 23 (11): 1249– 1265. CiteSeerX 10.1.1.14.8162 . doi : 10.1002/spe.4380231105 . S2CID 8822797 .

[9] Van Emden, MH (1970年11月1日). "アルゴリズム402：クイックソートの効率向上" . Commun. ACM . 13 (11): 693–694 . doi : 10.1145/362790.362803 . ISSN 0001-0782 . S2CID 4774719 .

[10] ベントレー、ジョン（2007）。「私が書いたことのない最も美しいコード」。オーラム、アンディ、ウィルソン、グレッグ（編）『美しいコード：一流プログラマーが語る思考法』。オライリー・メディア。30ページ。ISBN 978-0-596-51004-6。

[:1-11] 1 2 3 「クイックソート分割：Hoare vs. Lomuto」 . cs.stackexchange.com . 2015年8月3日取得.

[12] McIlroy, MD (1999年4月10日). "クイックソートのキラー敵対者" (PDF) . Software: Practice and Experience . 29 (4): 341– 344. doi : 10.1002/(SICI)1097-024X(19990410)29:4 < 341::AID-SPE237 > 3.0.CO ; 2-R . S2CID 35935409 .

[:3-13] 1 2ジョン・ベントレー (1999).プログラミングの真珠. アディソン・ウェスリー・プロフェッショナル。

[:2-14] 1 2 3 4コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2009) [1990]。「クイックソート」。アルゴリズム入門(第 3版)。 MIT プレスとマグロウヒル。ページ170–190。ISBN 0-262-03384-4。

[15] ワイルド、セバスチャン (2012)。Java 7 のデュアルピボットクイックソート(論文)。カイザースラウテルン工科大学。

[16] Hoare, CAR (1962年1月1日). "Quicksort" . The Computer Journal . 5 (1): 10– 16. doi : 10.1093/comjnl/5.1.10 . ISSN 0010-4620 .

[17] Chandramouli, Badrish; Goldstein, Jonathan (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 .

[sedgewickBook-18] 1 2セッジウィック、ロバート（1998年9月1日）。C言語によるアルゴリズム：基礎、データ構造、ソート、検索、パート1～4（第3版）。ピアソン・エデュケーション。ISBN 978-81-317-1291-7。

[glibc_qsort-19] GNU libcの qsort.c:、

[20] ttp://www.ugrad.cs.ubc.ca/~cs260/chnotes/ch6/Ch6CovCompiled.html

[sedgewickQsortPaper-21] 1 2 Sedgewick, R. (1978). "クイックソートプログラムの実装". Comm. ACM . 21 (10): 847– 857. doi : 10.1145/359619.359631 . S2CID 10020756 .

[LaMarca1999-22] 1 2 3 LaMarca, Anthony; Ladner, Richard E. (1999). " The Influence of Caches on the Performance of Sorting". Journal of Algorithms . 31 (1): 66–104 . CiteSeerX 10.1.1.27.1788 . doi : 10.1006/jagm.1998.0985 . S2CID 206567217.小さなサブ配列を最後に保存することは命令数の観点からは理にかなっているが、キャッシュのパフォーマンスの観点からはまさに間違った行為である。

[23] Umut A. Acar、Guy E Blelloch、Margaret Reid-Miller、Kanat Tangwongsan、「クイックソートとソートの下限」、並列および逐次データ構造とアルゴリズム、2013年。

[24] Breshears, Clay (2012). "Quicksort Partition via Prefix Scan" . Dr. Dobb's .

[25] ミラー、ラス；ボクサー、ローレンス（2000）。アルゴリズム逐次および並列：統一的アプローチ。プレンティスホール。ISBN 978-0-13-086373-7。

[26] Powers, David MW (1991).並列化されたクイックソートと基数ソートの最適な高速化. 並列コンピューティング技術に関する国際会議議事録. CiteSeerX 10.1.1.57.9071 .

[unbalanced-27] もう一方の要素は、ピボットがHoareのパーティショニングルーチンのようにサブパーティションのいずれかに含まれているか $、Lomutoのルーチンのように両方から除外されているかに応じて、 1つ$ $の$ 要素を持つか、空（0個の要素を持つ）になるかのいずれかになります。

[28] Motwani, Rajeev; Raghavan, Prabhakar (1995年8月25日). Randomized Algorithms . Cambridge University Press. ISBN 9780521474658。

[29] Ďurian, Branislav. 「スタックなしのクイックソート」. Mathematical Foundations of Computer Science 1986: Proceedings of the 12th Symposium . MFCS 1986. Bratislava, Czechoslovakia: Springer Berlin Heidelberg.

[30] 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}²⁸要素のソートでクイックソートより8倍以上遅い）。

[31] Hsieh, Paul (2004). "Sorting revisited" . azillionmonkeys.com.

[32] MacKay, David (2005 年 12 月). "ヒープソート、クイックソート、およびエントロピー" . 2009 年 4 月 1 日にオリジナルからアーカイブされました。

[Kutenin-LLVM-33] 1 2 Kutenin, Danila (20 April 2022). "Google の規模とそれを超える規模での std::sort の変更" . Experimental chill .

[34] Wild, Sebastian; Nebel, Markus E. (2012). Java 7 のデュアルピボットクイックソートの平均ケース分析。欧州アルゴリズムシンポジウム。arXiv : 1310.7409。Bibcode : 2013arXiv1310.7409W。

[:0-35] ヤロスラフスキー、ウラジミール (2009)。「デュアルピボットクイックソート」(PDF)。 2015年10月2日にオリジナル(PDF)からアーカイブされました。

[36] 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。

[37] 「配列」 . Java Platform SE 7. Oracle . 2014年9月4日取得。

[38] Wild, Sebastian (2015年11月3日). "なぜデュアルピボットクイックソートは速いのか？". arXiv : 1511.01138 [ cs.DS ].

[39] Kushagra, Shrinu; López-Ortiz, Alejandro; Qiao, Aurick; Munro, J. Ian (2014). Multi-Pivot Quicksort: Theory and Experiments . Proc. Workshop on Algorithm Engineering and Experiments (ALENEX). doi : 10.1137/1.9781611973198.6 .

[40] クシャグラ、シュリヌ。ロペス・オルティス、アレハンドロ。マンロー、J.イアン;チャオ、オーリック（2014 年 2 月 7 日）。マルチピボットクイックソート: 理論と実験(PDF) (セミナープレゼンテーション)。オンタリオ州ウォータールー。

[41] Motzkin, D.; Hansen, CL (1982), "最小限のスペース要件で効率的な外部ソート", International Journal of Computer and Information Sciences , 11 (6): 381–396 , doi : 10.1007/BF00996816 , S2CID 6829805

[42] David MW Powers、「並列統合：実践的な複雑性」、オーストラリア・アジアコンピュータアーキテクチャワークショップ、フリンダース大学、1995年1月

[43] Kaligosi, Kanela; Sanders, Peter (2006年9月11日～13日).分岐予測の誤りがクイックソートに与える影響(PDF) . ESA 2006: 第14回欧州アルゴリズムシンポジウム.チューリッヒ. doi : 10.1007/11841036_69 .

[44] エーデルカンプ、ステファン。ヴァイス、アルミン（2016年4月22日）。「BlockQuicksort: 分岐の予測ミスがクイックソートに影響しない仕組み」。arXiv : 1604.06697 [ cs.DS ]。

[45] Richard Cole、David C. Kandathil:「パーティションソートの平均ケース分析」、欧州アルゴリズムシンポジウム、2004年9月14～17日、ノルウェー、ベルゲン。出版： Lecture Notes in Computer Science 3221、Springer Verlag、pp. 240–251。

[ 1 ]

[ 2 ]

[ 3 ]。

[ 4 ] 。

[ 5 ]

[

[

[ 8 ]

[ 9 ]

[

[

[

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[

[

[ 25 ]

[

[ 27 ]

28

[ 29 ]

[

[

[

[

[

[

[

実験

[

[

[ 41 ]

[

[ 43 ]

[ 44 ]

[ 45 ]