0

クイック ソート アルゴリズムを実装しましたが、テストしたところ、入力配列の最初の要素 (ピボットを取得した要素) に最大の要素がある場合に失敗することがわかりました。これが私のコードです：

void partition(int *a,int size){
    if(size<=1){return;}
    int pivot=a[0];
    int left=0,right=0;
    for(left=1,right=size-1;left<=right;){    //was size-1
        if(a[left]>=pivot&&a[right]<=pivot) {
            swap(left,right,a);
        }

        if(a[left]<pivot){left++;}
        if(a[right]>pivot){right--;}
    }
    swap(0,right,a);
    partition(a,right-1);
    partition(&(a[right+1]),size-right-1);
}

失敗するいくつかのサンプル:

I/P 245  111  32    4
O/P 4   111  32  245     `

I/P 154   11   43  3  7
O/P   7   11   43  3  154

私が犯した可能性のある間違いは何ですか？

4

2 に答える 2

2

パーティション関数のピボットである配列に要素がある場合がありません。

推定arr = { 5, 5, 1 , 1, 5, } 

pivot = 5
iter1:
left=1, arr[left]=5 ; right=4,arr[right]=5
(swapping)
not increasing left nor decreasing right - since 5 < 5 == false ; 5 > 5 == false

次の反復では、同じシナリオが繰り返され、実際には無限ループが発生します。

これに対処する1つの方法は、「大きな」部分でも、正確にピボットであるすべての要素が増加し、要素を交換する場合arr[right] < pivot（ではない場合<=）、減少するright場合arr[right] >= pivot（ではない場合>）、次のように決定することです。

...
for(left=1,right=size-1;left<=right;){    //was size-1      
        if(a[left]>=pivot&&a[right]<pivot) { 
        //                         ^ note < not <=
        swap(left,right,a);
    }

    if(a[left]<pivot){left++;}
    if(a[right]>=pivot){right--;}
    //        ^ note >=
}
...
于 2012-12-09T18:41:39.993 に答える
2

さて、問題はここにあります：

partition(a,right-1); // <- It's partition(array,size)!

に変更します

partition(a,right);

そして、それはうまくいきます。理由は分かっていると思います。
パーティション関数が正しく機能するには、次の 2 つを指定する必要があります。

1) 作業する配列。
2) 要素の数、サイズ。

問題は、左側の部分配列を分割するための最初の再帰呼び出しにあります。  partition(a,right-1)

引数 2 の は、 実際には であるのに、size誤って であると指定されています。 right-1right

aこれは、インデックスからb(両方を含むb>=a) までの配列内の要素の数が であるという事実を使用して解決できますN= b-a+1。

ここではa=0、 、したがって、b=right-1左側のサブ配列の要素数= =です。sizeN(right-1)-(0)+1right

したがって、 が正しく機能するには、 のように呼び出す必要がありますpartition(a,right);。左のサブ配列は で終わりますがright-1、right-1+1=right要素があります。

いつも起こります:)

于 2012-12-09T18:53:16.470 に答える