-1

古いアルゴリズムのコースを更新するためにいくつかの練習問題を行っており、クイックソートを実装しようとしています。はい、製品コードで使用する必要があることはわかっていますstd::sortが、これは教育目的のためです:)

以下のコードがあります。配列内のすべての要素が一意である場合は機能しますが、要素が重複している場合は機能しません。どうして？私はどこでつまずいたのですか？

void quicksort(int arr[], int left, int right)
{
    // base case:
    if (left >= right)
        return;

    // alternative case:
    int pivot_index = (left + right)/2;
    int pivot = arr[pivot_index];

    int i = left, j = right;
    int tmp;

    while (i < j)
    {
        // scan from left until elem > pivot or left == right, 
        while (arr[i] < pivot)
            ++i;

        // scan from right until elem < pivot or right == left.
        while (arr[j] > pivot)
            --j;

        if (i < j)
        {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            ++i;
            --j;
        }
    }
    // recurse on left and right.
    if (i > left)
        quicksort(arr, left, i);
    if (i < right)
        quicksort(arr, i + 1, right);
}

void main()
{
    const int arr_size = 7;
    int arr[arr_size] = {1,2,4,3,9,5,2};
    quicksort(arr, 0, arr_size - 1);

    for (int i = 0; i < arr_size; ++i)
    {
        std::cout << arr[i] << ", ";
    }
}
4

2 に答える 2

4 
if (i > left)
    quicksort(arr, left, i);
if (i < right)
    quicksort(arr, i + 1, right);

2 つの等しい要素の配列があるとします。次にi == right、まったく同じ配列を何度も何度も並べ替えます...

配列に複数の要素が含まれている場合、ある時点でそれが発生する可能性が非常に高くなります。

繰り返される要素のもう 1 つの障害点は、次のとおりです。

int arr[5] = { 4, 8, 4, 5, 6 };

ピボットはインデックス 2 の 4 で、最初のスキャンi == 0との後j == 2、2 つの 4 が交換され、iインクリメント、jデクリメントさi == j == 1れ、ループが停止します。

再帰呼び出しは{ 4, 8 }respを並べ替えます{ 4, 5, 6}が、結果は正しく並べ替えられません。

スキャン条件の少なくとも 1 つをarr[i] <= pivotresp に置き換えることで、この問題を回避できます。arr[j] >= pivot、ただし、配列からはみ出さないようにする必要があります (ピボットが最大または最小の要素である場合) i < j。そこに条件を含めることをお勧めします。

場合は、resp。スワッピング時にインデックスをデクリメントし、

if (i < j)
{
    tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
    ++i;
    --j;
}

状況で最後のスワップが発生する可能性があるという問題が常にあります

... x y z ...
    ^   ^
    i   j

をi == j指すようになり、ピボットと比較するy方法についての情報がありません。y

yそのため、さまざまな可能性を調べて処理する必要があります。

ただし、要素が繰り返されないと、実装も正しくありません。検討

{ 1, 4, 5, 6, 9, 3, 2 }
           ^
         pivot

まず、iピボットを指すまで増加jし、2 を指したままになります。これら 2 つが入れ替わり、i増加、j減少するため、状況は次のようになります。

{ 1, 4, 5, 2, 9, 3, 6 }
              ^  ^
              i  j

arr[i] > pivot、およびarr[j] < pivot、スワップ、インクリメントi、デクリメントj：

{ 1, 4, 5, 2, 3, 9, 6 }
              ^  ^
              j  i

j < iこれで、ループは停止しますが、再帰呼び出しはandquicksort(arr, 0, 5);に対してquicksort(arr, 6, 6);行われるため、「ソートされた」配列の最後の要素は配列の最大要素ではありません。

于 2013-01-03T22:21:48.403 に答える
0

left == right の場合、フォールバックはありません。キャッチがない場合、コードは何も実行しません。

于 2013-01-03T22:19:28.697 に答える