0

デュアル ピボット クイックソート アルゴリズムを実装する課題があります。数値の少ないベクトルでは機能しているようですが、たとえば 100000 でベクトルをソートしようとすると、セグメンテーション違反が発生します。何か助けはありますか？ 

void quicksort_dual_pivot(vector <int> &A, int L, int R)
{

if(L>=R) return; 

 int spivot = A[L]; //Error here.
 int bpivot = A[R]; 


if(spivot > bpivot){

    swap(A[R],A[L]);
    swap(spivot,bpivot);
}

int l = L+1; 

int g =  R-1; 



for(int k=l;k<=g;k++){

    if(A[k] < spivot) {     


        swap(A[k],A[l]);
        l++;
    }

    else if(A[k] > bpivot){
        while(A[g] > bpivot && k  < g){

          g--;
        }

        swap(A[g],A[k]); 
        g--;

        if(A[k] < spivot){    

            swap(A[k],A[l]);
            l++;

        }
    }

}

l--;
g++;

swap(A[L],A[l]);

swap(A[R],A[g]);



quicksort_dual_pivot(A,L,l-1); 

quicksort_dual_pivot(A,l+1,g-1); // And error here.

quicksort_dual_pivot(A,g+1,R);

}

ありがとう。

4

1 に答える 1

1

デバッガーをアタッチします。

または、それをしたくない場合は、この直前に L を出力して再実行してください。

int spivot = A[L]; //Error here.

そして、あなたが得ているものを見てください。それはおそらく予期しないものです。次に、その値が再帰呼び出しでどのように渡されているかを調べ、何が悪い値を取得する原因になっているのかを調べます。配列の末尾から 1 つまたは複数の方向にインクリメントしていると思います。

于 2013-01-06T21:53:04.247 に答える