UDB UDB - 2 months ago 26
C++ Question

how to implement quick sort algorithm in C++

here is the of quick sort algorithm from the MITOcw(Introduction To Algorithms ) lecture

QUICKSORT(A,p,q)
if(p < q)
then r = PARTITION(A,p,q)
QUICKSORT(A,p,r-1)
QUICKSORT(A,r+1,q)

PARTITION(A,p,q)
x = A[p]
i=p
for j = p+1 to q
if A[j] <= x
then i = i+1
swap A[i] with A[j]
swap A[p] with A[i]
return i


and here its C++ implementation on an integer array

#include <iostream>

using namespace std;

void quickSort(int *,int,int);

int partition(int *, int,int);

int main()
{
int A[10]={6,10,13,5,8,3,2,25,4,11};
int p=0,q=10;

cout<<"======Original======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;

quickSort(A,p,q);

cout<<"======Sorted======="<<endl;
for(int f=0; f<10; f++)
cout<<A[f]<<endl;
}


void quickSort(int *A, int p,int q)
{
int r;
if(p<q)
{
r=partition(A, p,q);
quickSort(A,p,(r-1)); //I think the problem is here this first quickSort call
// is reducing the value of r and hence value of q becomes
// less than p recursively. How can I separate both calls
// one for left and one for right sub array of the pivot.
quickSort(A,(r+1),q);
}
}


int partition(int *A, int p,int q)
{
int x= A[p];
int i=p;
int temp;
int j;

for(j=p+1; j<q; j++)
{
if(A[j]<=x)
{
i=i+1;
temp= A[j];
A[j]=A[i];
A[i]=temp;
}

}

temp= A[p];
A[p]=A[i];
A[i]=temp;

return i;
}


code doesn't yield sorted array although the first two runs of quickSort function gives desired output. that is it place the first pivot element to its correct position

Answer

Your consideration is wrong. The value of r does not change, since it is given as value to the Quicksort function(not a reference). You handle the ranges with p,q such that p is the first index in the range and q the first index not in the range.

Thus, your calls were wrong:

r=partition(A, p,q);
quickSort(A,p,r); //range is from A[p] to A[r-1] 
quickSort(A,(r+1),q); //range is from A[r+1] to A[q-1]

Here is the complete example. I used std::swap to change elements and ans std::vector instead of an array.

#include <iostream>
#include <vector>

using namespace std;

void quickSort(vector<int>&,int,int);

int partition(vector<int>&, int,int);

int main()
{
    vector<int> A = {6,10,13,5,8,3,2,25,4,11};
    int p=0;
    int q=10;

    cout<<"======Original======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;    

    quickSort(A,p,q);

    cout<<"======Sorted======="<<endl;
    for(auto e: A)
        cout<< e <<" ";
    cout<< endl;   
}


void quickSort(vector<int>& A, int p,int q)
{
    int r;
    if(p<q)
    {
        r=partition(A, p,q);
        quickSort(A,p,r);  
        quickSort(A,r+1,q);
    }
}


int partition(vector<int>& A, int p,int q)
{
    int x= A[p];
    int i=p;
    int j;

    for(j=p+1; j<q; j++)
    {
        if(A[j]<=x)
        {
            i=i+1;
            swap(A[i],A[j]);
        }

    }

    swap(A[i],A[p]);
    return i;
}

Live example: ideone

Comments