9

Robert Sedwick Algorithms and data structure part 1-4 の本でクイックソートアルゴリズムを読んでいます。

template <class item>

static void quicksort(item [] a, int l, int r)
{
    if(r <= l) return;
    int i = partition(a,l,r);
    quicksort(a, l, i-1);
    quicksort(a, i+1, r);
}

template <class item>
int partition(item a[], int l, int r)
{
    int i = l-1; j = r; item v = a[r];

    for(;;) {
        while( a[++i] < v );
        while( v < a[--j] ) 
            if( j == l ) 
                break;
        if( i >= j) 
            break;  // pointer crossing.
        exch(a[i], a[j]);
    }

    exch(a[i], a[r]);
    return i;
}

本には、上記のアルゴリズムに関する次のテキストがあります。

ファイル内に重複キーが存在する場合、ポインターの交差は微妙です。i < j のときにスキャンを終了し、i-1 ではなく j を使用して、最初の再帰呼び出しの左サブファイルの右端を区切ることで、分割プロセスをわずかに改善できます。この場合、ループをもう 1 回繰り返すことで改善が見られます。スキャン ループが j と i で同じ要素を参照して終了するたびに、最終的な位置に 2 つの要素が残るためです。つまり、両方のスキャンを停止した要素です。したがって、これは分割要素および分割要素自体と等しくなければなりません。この特定のケースでは、プログラムは a[r] のパーティション キーと等しいキーを持つレコードを残すため、この変更はおそらく行う価値があります。

私の質問は

  1. 上記のプログラムを以下の説明でどのように変更できますか? テキストを理解するためにそれを変更するのに苦労しています。
  2. 重複キーがさらに存在すると、上記のクイックソートアルゴリズムが効果的に機能しないのはなぜですか。
  3. より多くの複製キーが存在する場合、上記の変更はどのように改善されますか?
  4. 著者は、「コールの最初のパーティションはクイックソート（a、i + 1、r）縮退します。その右端のキーが最小であるため」とはどういう意味ですか。? ここで、著者は退化とはどういう意味ですか?

お時間をいただきありがとうございます。

4

1 に答える 1

6

>>重複するキーがさらに存在する場合、上記のクイックソートアルゴリズムが効果的に機能しないのはなぜですか？

破壊条件が次のようになるため、非効率になります。if(i >= j) break;
したがって、とを使用して両側からスキャンするiと、 i == jのときに、を超えるのではなくj破壊する可能性があります。重複するキーが多数存在する場合に中断すると、 どのような問題が発生する可能性がありますか？ij

i==j

最初のwhileループからブレークするときは、2番目のwhileループからブレークi==j;する必要があります が、次の「ブレーク」を検討しているため、つまり、ピボット要素と同じです。a[i] >= va[j] <=vi==ja[i] = a[j] = va[i]v

このようなシナリオでは、最も外側のexch(a[i], a[r]);値がピボット値をそれ自体に交換するだけです。
したがって、配列の右半分の次の再帰呼び出しquicksort(a, i+1, r);では、最小要素が右端に配置されます（ピボット選択戦略は単純ですitem v = a[r];）。QuickSortがピボット要素を選択するのは悪いことです。アレイの最小値または最大値になります。したがって、その後の右半分の再帰呼び出しは、縮退したものになります。
そのため、作成者はi == jを壊さずに、それが発生する直前にそれらをキャッチするようにアドバイスしています。

>>ここで縮退するとはどういう意味ですか？

ここでの縮退とは、再帰ツリーが歪んでいることを意味します。つまり、後続の問題はほぼ同じサイズで生成されていません。サイズの問題をサイズのN問題のようなものに分割し、サイズN-1 と1の問題に分割するようなよりバランスの取れたものではありN/2ませんN/2。

>>上記のプログラムを以下の説明でどのように変更できますか？

次のように実装できます。

int partition(int A[], int l, int r){
        int i=l-1, j=r, v = A[r];
        for(;;){
                while(A[++i] < v);
                while(A[--j] > v)
                        if(j == l)
                                break;
                if(i>=j)
                        break;
                swap(A[i], A[j]);
        }
        if(i == j){// case when we stopped at the pivot element.
                j = j+1;//backtrack j 1 step.
                if(j <= r)
                    swap(A[j], A[r]);
                return j;// partition the subsequent problems around j now.
        }
        swap(A[i], A[r]);
        return i;
}

>>より多くの複製キーが存在する場合、上記の変更はどのように改善されますか？
退化したケースの明らかなシナリオを生成しないようにすることで、パフォーマンスが向上します。

于 2012-11-12T09:25:14.813 に答える