3

Jon Bentley が彼の「美しいクイックソート コード」を紹介しているhttp://code.google.com/edu/algorithms/index.htmlのビデオを見るまでは、クイックソートの仕組みをよく理解していると思っていました。 :

void quicksort(int l, int u){
    int i, m;
    if(l >= u) return;
    m = l;
    for(i = l+1; i<= u; i++)
        if(x[i] < x[l])
            swap(++m, i); //this is where I'm lost. Why the heck does it preincrement?

    swap(l, m);

    quicksort(l, m-1);
    quicksort(m+1, u);

}

私を混乱させるアルゴの別の部分は、FOR ループの後の最後のスワップです。なぜそれが必要なのですか？配列がすでに整っていると仮定しましょう。そうであれば、x[i] > x[l] であるためスワップは発生しません。最後に、l を m に置き換えます。それは注文を台無しにします。

何か不足していますか？

ありがとう。

4

5 に答える 5

6

最初mに を に設定しl、要素x[l]を分割要素 (ピボット) として選択します。

次に、アルゴリズムはリストを繰り返し処理し、 より小さい要素を見つけるたびに、現在の の直後にx[l]移動します。つまり、 の場合、 からまでのすべての位置にある要素は、 要素より小さいことを意味します。 mm > ll+1mx[l]

例えば：

3 5 4 2 1  l = 0, m = 0, i = 1
  ^
3 5 4 2 1  l = 0, m = 0, i = 2
    ^
3 2 4 5 1  l = 0, m = 1, i = 3
      ^
3 2 1 5 4  l = 0, m = 2, i = 4
        ^

そして最後に、最後の小さい数字を最初の (分割) 要素と交換して、次を取得します。

1 2 3 5 4

最初の要素より小さい要素がない場合、スワップは何もしません (mが に等しいためl)。

于 2012-04-06T21:51:09.090 に答える
1

パーティション アルゴリズムは優れており、覚えやすいです。それは ACM の通信に掲載されているか、Benltey によって何度も語られています。Bentley の Programming Pearls book にも掲載されています。アイデアは、事後条件を否定する要素を追跡することです。つまり、ピボットの後ろの要素は少なくなり、インデックスの上にある要素は大きくなります。しかし、ランダムな要素の選択がランダムでない場合、最大 (または最小) の要素になってしまう可能性があり、O(n) に対してさらに多くのスワップを行う必要があります。Java での実装と説明は [ブログ]: http://harisankar-krishnaswamy.blogspot.in/2013/05/quick-sort-partition-algorithm.html「こちら」

ハリ

于 2013-05-19T04:36:59.233 に答える
1

要素 atx[l]は、選択されたピボットです。for ループの不変条件は、通過するすべての要素がピボットよりも小さく、x[l+1]通過するすべての要素がピボットよりも大きいか等しいことです。x[m]x[m]x[i]

ピボットよりも小さい要素を見つけると、それを entry まで下に移動しm+1、次にバンプアップしmます。( のエントリm+1はピボットよりも大きいため、上に移動しても問題ありません。)

最後のスワップは、ピボットを下のアレイと上のアレイの間に配置する必要があるため、ピボットを からx[l]に移動することです。x[m]スワップが発生しない場合 (並べ替えられた配列の例)、m==l最後のスワップでは何も移動しません。

コードは、代わりに設定m = l + 1して使用する方が教育的に明確になります。m++++m

于 2012-04-06T21:50:57.620 に答える
0

ソートされる部分配列の最初と最後の要素への固定インデックスlとポイント。u値x[l]は常にピボットとして選択されます。

ループの上部で、サブ配列 ( pivot を除くx[l]) は次のように分割されます。

  • 下の領域: インデックスを持つ要素l < index <= mがテストされ、< x[l]
  • 中間領域: インデックスを持つ要素m < index < iがテストされ、>= x[l]
  • 上の領域: インデックスを持つ要素はi <= index <= uまだテストされていません

考えられる混乱の原因の 1 つは、ループの実行中に、ピボットよりも大きな値を持つ領域が上部ではなく中央のセクションであることです。テストされていない領域が使い果たされるまで、配列の上部に到達しません。拡張する下部領域のためのスペースを作るために、スワップを繰り返すことによって効果的に「移動」されます。

具体的には、ループ変数mは、下部領域の拡張が必要になるたびに事前にインクリメントされます。下部領域を拡張するには、中央領域の最初の要素 (存在する場合) を最後に移動する必要があります。中間領域が空の場合m == i、プレインクリメントの後 (この場合、swap()操作はノーオペレーションでなければなりません) に注意してください。

最後に、再帰的なステップのために配置するために、ピボットx[l]が下部領域の最後にスワップされます。配列がすでに整っている場合、下の領域は空でm == lあり、最後のswap()操作は再びノーオペレーションであることに注意してください。

于 2012-04-06T22:40:54.650 に答える
0

配列がソートされている場合、m は初期値の l から変化しないため、スワップは何もしません。

于 2012-04-06T21:53:30.710 に答える