41

3 ウェイ パーティションの QuickSort とは何ですか?

4

7 に答える 7

55

配列を想像してください：

3, 5, 2, 7, 6, 4, 2, 8, 8, 9, 0

2パーティションのクイックソートは、たとえば4の値を選択し、配列の片側に4より大きいすべての要素を配置し、反対側に4未満のすべての要素を配置します。そのようです：

3, 2, 0, 2, 4, | 8, 7, 8, 9, 6, 5

3パーティションのクイックソートでは、2つの値を選択してパーティションを作成し、その方法で配列を分割します。4と7を選択しましょう：

3, 2, 0, 2, | 4, 6, 5, 7, | 8, 8, 9

これは、通常のクイックソートのほんのわずかなバリエーションです。

配列がソートされるまで、各パーティションのパーティション分割を続けます。ランタイムは技術的にはnlog3 （ n）であり、通常のクイックソートのnlog 2 （n）とはわずかに異なります。

于 2009-06-02T19:36:15.343 に答える
18

http://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdf

以下も参照してください。

http://www.sorting-algorithms.com/quick-sort-3-way

インタビューの質問バージョンも面白いと思いました。それは尋ねます、クイックソートの4つのパーティションバージョンがあります...

于 2009-06-02T19:30:27.193 に答える
15

パーティションの数をパラメーターとして残してAkra-Bazziの式を使用して計算を実際に行い、そのパラメーターを最適化すると、e（= 2.718 ...）パーティションが最速のパフォーマンスを発揮することがわかります。ただし、実際には、言語構造、CPUなどはすべて二項演算用に最適化されているため、2セットへの標準的なパーティション分割が最速になります。

于 2009-06-02T21:16:18.930 に答える
15

三方仕切りはDjstrka製だと思います。

要素を持つ配列について考えてみてください{ 3, 9, 4, 1, 2, 3, 15, 17, 25, 17 }。

基本的に、特定のピボットよりも小さい、等しい、大きいという 3 つのパーティションを設定します。equal-to パーティションは、すべての要素が既に等しいため、さらに並べ替える必要はありません。

たとえば、最初3の要素をピボットとして選択すると、ダイクストラを使用した 3 分割は元の配列を配置して 2 つのインデックスを返しm1、m2インデックスが より小さいすべての要素が よりm1も低くなり3、インデックスがより大きいすべての要素が以下m1はm2に等しくなり3、インデックスが より大きいすべての要素は よりもm2大きくなり3ます。

この特定のケースでは、結果の配列は{ 1, 2, 3, 3, 9, 4, 15, 17, 25, 17 }であり、値m1およびm2はm1 = 2およびm2 = 3です。

結果の配列は、分割に使用される戦略によって変わる可能性がありますが、数値m1と数値m2は同じになることに注意してください。

于 2013-10-10T15:23:49.093 に答える
1

これは、パーティションがピボットよりも小さい、等しい、および大きい要素であるダイクストラのパーティション分割方法に関連していると思います。小さいパーティションと大きいパーティションのみを再帰的にソートする必要があります。インタラクティブなビジュアライゼーションを見て、クルミでそれで遊ぶことができます。私が使用した色は、赤/白/青です。これは、パーティション分割の方法が通常「オランダ国旗問題」と呼ばれているためです。

于 2015-07-28T22:02:50.143 に答える