3ウェイ・パーティショニングのアルゴリズム

Question

3ウェイ・パーティショニングは、配列を3つのサブ配列：要素<ピボット、要素==ピボット、要素>ピボットに分割します。

我々はそれを行うためにE.ダイクストラの「オランダの旗問題」のためのよく知られたソリューションを使用することができますが、Bentley and McIlroyは残念ながら別のway（「高速3ウェイ分割を」セクション＃22を参照）

示唆します私は理解していないどのようにアルゴリズムがより良い（高速）です。誰もそれをゆっくり説明できますか？

Answer 1

少なくとも、配列内に異なる要素が少なすぎない間は、平均スワップ回数が少なくなります。すなわち

n - multiplicity(pivot) 

スワップですので

「オランダ語フラグ」アルゴリズムは、ピボットに等しくない要素ごとに1つのスワップを使用します。

ピボットに等しい要素を最初に配列の両端にスワップする代わりに、ピボットに等しい各要素を2回（一方は片側、最後は中央）スワップし、a[i], a[j]をi < jにスワップしますa[j] < pivot < a[i]、つまり

2*multiplicity(pivot) + count(bad_pairs) 

スワップです。悪いペアの数は(n - multiplicity(pivot))/2以上でなければならず、通常は（ランダムな配列）小さくて、頭の上から外れています。私は平均で(n-multiplicity(pivot))/4以下のようなものを期待しています。だからmultiplicity(pivot) < n/5の場合は、スワップ回数を減らすことが保証されています。もし私の見積もりが正しければ、スワップ回数は平均してmultiplicity(pivot) < 3*n/11になります。

アレイ内に別個の要素がごくわずかしかないことがわかっている場合は、 "Dutch Flag"が優れていると思うが、一般的には、スワップ回数が少なくなるまでソートされる部品はかなり小さくなっています。