c++ - 双轴快速排序

Question

我有一个任务来实现一个双轴快速排序算法。它似乎适用于具有少量数字的向量，但是当我尝试使用例如 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);

}

谢谢。

Answer 1

附加调试器。

或者，如果您不想这样做，请在此之前打印出 L 并重新运行。

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

看看你得到了什么。想必是意料之外的事情吧。然后看看这个值是如何在递归调用中传递的，看看是什么导致你得到一个错误的值。我敢打赌你会在一个或多个方向上从数组的末尾递增。