1

Trying to implement a Quick Sort algorithm.I think the problem is with the recursion, but I do not know what I should do to fix it. The program continues to crash every time I run it, and I cannot understand why. Here is the code:

#include<iostream>

using namespace std;
int pIndex;

int Partition(int *A,int start,int end){

int pivot;
int pIndex;
 if(start<end){
    int pivot=A[end];
    int pIndex=start;
    for(int x=0;x<end;x++){
        if(A[x]<A[end]){
            swap(A[x],A[pIndex]);
             pIndex=pIndex+1;   
        }   
    }
    swap(A[pIndex],A[end]);
 }
//cout<<pIndex<<endl;
swap(A[pIndex],A[end]);
return pIndex;
};
void QuickSort(int *A, int start,int end){
    if(start<end)
    {

    pIndex=Partition(A,start,end);
    QuickSort(A,pIndex+1,end);
    QuickSort(A,start,pIndex-1);
}
};
int main(){

int A[10]{4,23,1,43,2,10};  
//Partition(A,0,9);
QuickSort(A,0,5);
for(int x=0;x<10;x++){
    cout<< A[x]<<" ";
}
}
3
  • 3
    Have you tried running the program under a debugger? What line does it show the crash on? Commented Oct 6, 2014 at 3:09
  • You should not put a semicolon after the } at the end of a function; it is a null statement or null declaration. That is, however, completely unrelated to your crash. Commented Oct 6, 2014 at 3:10
  • The answer given solves your crash, however, I think you have to revisit the logic of your algorithm since partition will never work as you expect. Commented Oct 6, 2014 at 3:24

3 Answers 3

3

Your partition algorithm is about twice as much code as it needs to be. You seem to be always choosing the last element in the sequence for your pivot, and although not advisable, it will work for academic demonstration.

Your Crash

You're defining two pIndex values, only one of which is actually deterministic. You also declare two pivot variables, but that does NOT cause your crash (the first one is never used). It should be cleaned up none-the-less, but the death knell in your code is duplicate pIndex

int pivot;
int pIndex;     // HERE
if(start<end){
    int pivot=A[end];
    int pIndex=start; // HERE AGAIN
    for(int x=0;x<end;x++){
        if(A[x]<A[end]){
            swap(A[x],A[pIndex]);
            pIndex=pIndex+1;   
        }   
    }
    swap(A[pIndex],A[end]);
}
swap(A[pIndex],A[end]); // uses non-determined pIndex
return pIndex; // returns non-determined pIndex

Changing int pIndex=start; to simply be pIndex=start; will solve your crash, but your partition method still needs... help.


The "Sweep" Partition Method

The "sweep" method of partitioning is generally done like this for a pivot value that is assumed to be right-tailed, and you would be hard pressed to get this simpler (invoking std::partition not withstanding):

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<end; ++i)
    {
        if (A[i] < a[len-1])
            std::swap(A[i], A[pvt++])
    }
    std::swap(A[pvt], a[len-1]);
    return pvt;
};

The above algorithm includes only the necessities needed for a partition: the sequence iterator (a pointer in your case), and the sequence length. Everything else is deterministic based on those two items. A quick sample program of how this works follows, with a purposely placed 5 for the pivot value:

#include <iostream>

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
            std::swap(A[i], A[pvt++]);
    }
    std::swap(A[pvt], A[len-1]);
    return pvt;
};

int main()
{
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 };
    size_t n = Partition(arr, sizeof(arr)/sizeof(*arr));
    std::cout << "Partition : " << n << '\n';
    for (auto x : arr)
        std::cout << x << ' ';
    std::cout << '\n';
}

Output

Partition : 4
4 3 2 1 5 7 8 6 9 

How To Invoke From QuickSort

Invoking a partition in quicksort sets up the pivot location, which becomes the "end" iteration point of the bottom segment, and the one-BEFORE iteration point of the top segment. It is critical the pivot location returned from an invoke of Partition() should NOT be included in either subsequence when recursing.

void QuickSort(int *A, size_t len)
{
    if (len < 2)
        return;

    size_t pvt = Partition(A, len);
    QuickSort(A, pvt++);        // NOTE: post increment...
    QuickSort(A+pvt, len-pvt);  // ...which makes this skip the pivot
}

Yeah, pointer arithmetic rocks, don't you think?


Putting It All Together

The program below incorporates both the Partition and QuickSort :

#include <iostream>

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
            std::swap(A[i], A[pvt++]);
    }
    std::swap(A[pvt], A[len-1]);
    return pvt;
};

void QuickSort(int *A, size_t len)
{
    if (len < 2)
        return;

    size_t pvt = Partition(A, len);
    QuickSort(A, pvt++);            // NOTE: post increment
    QuickSort(A+pvt, len-pvt);
}

int main()
{
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 };
    QuickSort(arr, sizeof(arr)/sizeof(*arr));
    for (auto x : arr)
        std::cout << x << ' ';
    std::cout << '\n';
}

Output

1 2 3 4 5 6 7 8 9 

I hope it helps.

Sign up to request clarification or add additional context in comments.

1 Comment

Thank you so much, this fixed the issue. I appreciate all the work put into your post :) Thank you
1

In this part:

int pivot;
int pIndex;
 if(start<end){
    int pivot=A[end];
    int pIndex=start;

You are defining two pivots, and two pIndex's. You are not using the pivot at all, and with the last swap you are using the uninitialized pIndex. This should work:

int Partition(int *A,int start,int end){    
    int pIndex = start;
    if(start<end){
        for(int x=0;x<end;x++){
            if(A[x]<A[end]){
                swap(A[x],A[pIndex]);
                pIndex=pIndex+1;   
            }
        }
        swap(A[pIndex],A[end]);
    }   
    swap(A[pIndex],A[end]);
    return pIndex;
}

2 Comments

That does not work. The output is 23 10 2 43 4 1 0 0 0 0 (although it does not crash at least)
When I substitute this function in, it does fix the crash. but absolutely nothing appears on the screen.
1

I'm also something of a C++ newbie, but I find myself curious about what happens when start >= end. It looks as though your Partition function will still return a pIndex value, but I don't see where you define it anywhere. If (as I suspect) it returns whatever value happens to reside in memory, then you'll very likely end up referencing some undefined memory locations when you use A[pIndex]

1 Comment

your observation of pIndex never being set is spot-on.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.