1

以下は、Hoare与えられたピボットに基づいて配列を分割するために私が書いた分割アルゴリズムです (この場合、それは配列の最初の要素であり、かなり悪い選択です!)。ただし、Bentley-McIlroy 3-way partitioninghttp ://www.sorting-algorithms.com/static/QuicksortIsOptimal.pdfでは、キーの数が等しい場合にパフォーマンスが向上すると主張しています。Hoare9ページのコードが何を達成するのか、なぜアルゴリズムよりも優れたパフォーマンスを発揮するのか、簡単に説明できる人はいますか? <そして、1 つの質問として、パーティショニングは、=およびに基づいて要素を配置し>ます。複数回存在する要素がピボットでない場合はどうなりますか?

def hoare(arr,start,end):
     pivot = arr[start]
     i,j = start,end
     while i < j:
        while i < j and arr[i] <= pivot:
            i += 1
        while j >= i and arr[j] > pivot:
            j -= 1
        if i < j:
            arr[i],arr[j] = arr[j],arr[i]
     arr[start],arr[j] = arr[j],arr[start]
     return j
4

2 に答える 2

5

N. Lumoto のアイデアに基づいて、3 ウェイ パーティションを実装することが可能であることがわかりました。これは少し簡単です。(Jon Bentley が著書「Programming pearls」で述べたように、Lumoto の方法は簡単です)。

アイデアは、スキャン中に不変条件を維持することです。ピボットよりも小さい要素は常に左端のセクションに配置され、ピボットに等しい要素はそのセクションの隣にあり、ピボットよりも大きい要素は常に左端に配置されます。ピボットは最も右側に配置されます。残りの部分は、まだ検査されていない要素です。

iこれらのセクションは、 、k、および で囲まれていjます。要素を調べるとき、ピボットと等しい場合は次の要素に進み、ピボットより小さい場合は、「等しい」セクションで最初の要素と交換できるため、不変条件は次のようになります。再開しました。それ以外の場合は、より大きなセクションの前の最後のものと交換し続ける必要があります。

/*
 * Another 3-way partition ternary quick sort based on N. Lomuto's method.
 *   Invariant: ... less ... | ... equal ... | ... ? ... | greater |
 *                           i               k           j
 */
void qsort3(Key* xs, int l, int u) {
    int i, j, k; Key pivot;
    if (l < u - 1) {
        i = l; j = u; pivot = xs[l];
        for (k = l + 1; k < j; ++k) {
            while (pivot < xs[k]) { --j; swap(xs[j], xs[k]); }
            if (xs[k] < pivot) { swap(xs[i], xs[k]); ++i; }
        }
        qsort3(xs, l, i);
        qsort3(xs, j, u);
    }
}

標準ライブラリの qsort API に対して 100,000 要素でこのプログラムをテストしました。

于 2013-03-12T08:30:00.973 に答える
4

9ページのコードは、8ページの図でかなりよく説明されていると思います。最初にパーティションを作成しますが、ピボットに等しい要素をベクトルのエッジにスワップするため、最終的には次のようになります。

[equals-left] [lesses] [greaters] [equals-right]

次に、等しい要素を中央に戻します。

[lesses] [equals-left] [equals-right] [greaters]

次に、再帰的に並べ替え[lesses]て[greaters]

セジウィックの仮定は、データセット内で繰り返される多くの要素があるということです。その場合、ピボットが繰り返されるのが一般的です。そうであれば、いずれのクイックソート再帰にもピボットの繰り返しを含めないことで、ある程度のメリットが得られるため、合計のサイズは2つのパーティションは、ピボットの繰り返し回数だけベクトルのサイズよりも小さくなります（それ自体であっても）。これにより、再帰する必要のある要素の数が減り、再帰が速くなります。

これを行うためのコストは、要素ごとに1つまたは2つの追加の比較ですが、どちらも以前の比較を異なる成功条件で繰り返すだけです。比較が複雑な場合は、最後の<比較の結果を保存できるようにするために、明示的な3者間比較関数を使用することをお勧めします（Sedgwickのコードのwhileループ内）。ピボットが繰り返されない場合、それはまさに追加コストです：それらの追加の比較。ピボットが繰り返される場合、繰り返されるピボット要素ごとに1つまたは2つの追加のスワップと2つまたは1つの追加の比較（つまり、スワップと比較に同じ時間がかかる場合は3つの追加の操作）に加えて、他の要素。

これは価値がありますか？私は懐疑的ですが、セジウィックがそう言った場合は、おそらく私ではなく彼の言うことに耳を傾けるべきです。

于 2012-09-25T16:54:04.760 に答える