CODEWITHSUNDEEP
c++quicksortcorruption
Mike
Mike

Reputation: 477

Quick Sort Error: stack around the variable was corrupted?

I am implementing a quick sort function for class. We have to do it the same way she taught us in class with her pseudocode, or else we dont get credit.

I am getting a runtime error that says "Stack around the variable 'quickArray' was corrupted"

I played with the debugger ,and still cannot figure out what the problem is. Im thinking that it has something to do with my Partition() function, but Im not sure. Can anyone help? Iv posted the main(), QuickSort(), and Partition() function below.

int main()
{


int quickArray[10] = { 5 ,99, 32, 4, 1, 12, 15 , 8, 13, 55};
int P = quickArray[0];
int R =quickArray[9];

QuickSort(quickArray,P,R);
return 0;

}

..........................................................................................

void QuickSort(int ar2[],int P, int R)
{
int Q;

if( P < R )
{
    Q =  Partition(ar2,P,R);
    QuickSort(ar2,P,Q-1);
    QuickSort(ar2,Q+1,R);
}

}

...........................................................................................

int Partition(int ar2[],int P, int R)
{
int x = ar2[R];
int i = P-1;
int temp;

for(int j = P; j <= R-1; j++)
{
    if( ar2[j] < x  )
    {
        i = i +1;
        temp = ar2[i];
        ar2[i] = ar2[j];
        ar2[j] = temp;
    }

    temp = ar2[R];
    ar2[R] = ar2[i+1];
    ar2[i+1] = temp;
}

return (i+1);
}

Upvotes: 1

Views: 468

Answers (3)

Shafik Yaghmour
Shafik Yaghmour

Reputation: 158619

You are passing the actual elements of the array not the indexes, a quick way to have debugged this would be a cout at the top of QuickSort like so:

void QuickSort(int ar2[],int P, int R)
{
   std::cout << "P: " << P << " R: " << R << std::endl ;
   ...

and also a cout after the Partition call:

  Q =  Partition(ar2,P,R);

  std::cout << "QS: Q= " << Q << std::endl ;

the fix would be to call QuickSort from main like so:

 QuickSort(quickArray,0,9);

Spending some time with the debugger in the long term will help you spot these bugs much faster.

Upvotes: 2

Mitch Wheat
Mitch Wheat

Reputation: 300769

This

int P = quickArray[0];
int R = quickArray[9];

QuickSort(quickArray,P,R);

Should be this:

int arrStartIndex = 0;
int arrEndIndex   = 9;

QuickSort(quickArray, arrStartIndex , arrEndIndex);

As pointed out by others, your code should use more descriptive names.

Upvotes: 0

taocp
taocp

Reputation: 23664

You are passing wrong indices into the QuickSort function:

int P = quickArray[0];
int R =quickArray[9];

P and R are array indices, should be 0 and 9 in this case, however, you were passing the first element and last element as index into QuickSort, 55 (quickArray[9]) is out of index bound of quickArray, so you got the error.

BTW: it is better to use descriptive variable names, P and R do not well expressed what they mean in this case. You may use left, right, and pivot to replace R, R and Q, respectively as described in the QuickSort algorithm.

Upvotes: 2

Related Questions