そこからランダム化されたクイックソートのランダム化

Question

Cormenは、クイックソートでランダムなピボットを選ぶことの利点について簡単に語っています。しかし、指摘されているように ここ（4番目から最後の段落）：

乱数ジェネレーターを使用して位置を選択するのは比較的高価です

では、実際にランダムなピボットを実際に実装するのはどのようにして、どのようにランダムに実装されていますか？クイックソートの他の$ cal {o}（n lg n）$ sortに対する主な利点の1つを理解していることから、ピボットを選ぶサイクルを支出することは、それを弱体化させるので、それはあまりにも高価になることはありません。アドバンテージ。

編集

例として、 C からのコード」3つの美しいクイックソート「実際に電話します C 図書館 rand 働き：

int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

ここのピボットピッキングコードは明らかに$ cal {o}（1）$ですが、ここの隠された$ c $は比較的高いようです。

Answer 1

McillroyとDouglasの「クイックソートの殺人者の敵」（ソフトウェア - 実践と経験29（4）：341-344（1999））またはCrosby and Wallach'sをご覧ください 「アルゴリズムの複雑さ攻撃によるサービスの拒否」 のために 理由 ランダム化の背後。 QuickSortが動作します 非常に 毎回ピボットとして（ほぼ）最大/最小を選択した場合、ひどく。ランダム化が理にかなっているためには、そうする必要があります なれ ランダム（ピボットを選ぶ方法がわかっている場合 決定論的に, 、私はあなたが$ o（n^2）$の動作を強制するアレイを調理することができます。詳細については、記述された論文を参照してください）。しかし、派手なRNGは、たとえば、3つまたは別の小さな奇数の要素を摂取し、それらの中央値をピボットとして選択するよりも費用がかかります。これは、悪い行動に対抗する別の方法です。したがって、ランダム化を選択した場合は、aを使用します 速い rng seeded appropietly（おそらくa 線形合同 スキームで十分です）。

アルゴリズムは$ o（ cdot）$で比較することができますが（ cdot）$を比較できますが、同じアルゴリズムの異なる実装について話している場合は、より詳細な分析に切り替える必要があります。実際、SedgewickとFlajolet In 「アルゴリズムの分析の紹介」 $ t（n）= o（f（n））$をまったく使用すべきではないが、$ t（n） sim f（n）$ typeの無症候性を取得するよう努めるべきだと主張します。

Answer 2

したがって、時間をかけて座って実際にベントレーのGoogle講義を見た後、 3つの美しいクイックソート, 、ランダム化されたピボットのことがわかりました そうではありません 他の方法よりも速い。具体的には、Bently -Who with mcilroyによると、 標準CライブラリQSORT関数, 、私たちは彼らの論文から以下を持っています、 ソート関数のエンジニアリング:

• $ 1.386 ; cdot n lg n $最初、中央、またはランダム化されたピボットを使用した平均比較
• $ 1.188 ; cdot n lg n $ 3ピボットの中央値を使用した平均比較
• $ 1.094 ; cdot n lg n $ 3中央値ピボットの中央値を使用した平均比較

上記の論文によると：

したがって、最終コードでは、小さなアレイの中央要素、中サイズのアレイの最初の、中央、最後の要素の中央値、および大型アレイの9つの均等に間隔を置いた要素の擬似メディアンを選択します。

以下を読みました cを使用したデータ構造, 、テネンバウム、ラングサム、アウゲンシュタイン：

並べ替えられたファイルのクイックソートをスピードアップすることが可能です ランダム ピボット値として各サブファイルの要素。ファイルがほぼソートされていることがわかっている場合、これは良い戦略かもしれません（ただし、その場合、中央の要素をピボットとして選択することはさらに良いでしょう）。 ただし、ファイルについて何もわかっていない場合、そのような戦略は最悪の場合の動作を改善しません, 、毎回選択されるランダム要素が一貫して各サブファイルの最小の要素である可能性があるため（おそらくありますが）可能です。実用的な問題として、ソートされたファイルは、最小の要素を繰り返し選択するために起こっている良好な乱数ジェネレーターよりも一般的です。

彼らの本では、彼らはHoareパーティションスキームを使用しています。さらに彼らは言う：

ただし、平均して（サイズ$ n $のすべてのファイル以上）、クイックソートは、変更されていないバージョンでも約1.386 n lg n $の比較を行うことが示されます。

彼はここで最初の要素をピボットとして選ぶことを参照しています。

編集

ピボットの決定論的選択がランダム化されたものよりも優れていることに対する答えにつまずいたと思います。

質問9.3-3コルメンの「」最悪の場合、$ O（n lg n）$時間でQuickSortを実行する方法を示します。"

答えは、決定論的選択を使用して、毎回中央値要素を選択することです。決定論的選択は$ o（n）$の最悪の場合に実行されるため、最悪の場合は再帰$$ t（n）= 2t（n/2）+θ（n）=θ（n lg n）$$を取得します。この決定論的なクイックソートは、確かにそこに大きな隠された一定の要因があります。

曲がっていることは、擬似中央値を使用したこのアイデアの延長だと思います。 Bentelyの論文は、これらの擬似中央値の品質を定量化する別の論文を参照しています。

擬似中央値を計算するコストは$ theta（1）$ですが、実際の中央値を見つけるのは$ o（n）$です。これはおそらく、彼の非常に小さな一定の要因がどこから来たのかの大きな部分です。私は、紙の中央値が上記の実行時間を与えるためにパーティション関数によって十分な割合の良い分割を保証するのに「十分に良い」ことを何らかの形で紙のように参照していると思います。