how to implement quick sort algorithm in C++

Question

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 1

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

Answer 2

This is a template based solution. However, it works only for arrays of elements for now. If anyone has an improvement to make it generic for both arrays and STL containers, please do so.

template<typename T, typename compare = std::less<T>>
void q_sort(T input[], int l_idx, int r_idx, compare comp = compare()) {

    if (l_idx >= r_idx)
        return;

    // The below is the partition block (can be made a sub function)

    int left = l_idx;
    int right = r_idx;
    {
        int pivot_idx = l_idx;
        T pivot = input[pivot_idx];

        while (left < right) {
            while (comp(input[left], pivot))
                left++;
            while (comp(pivot, input[right]))
                right--;
            swap(input[left], input[right]);
        }

        swap(pivot, input[left]);
    }

    q_sort(input, l_idx, left, comp);
    q_sort(input, left+1, r_idx, comp);

}

template<typename T, typename compare = std::less<T>>
void quick_sort(T array[], int N, compare comp = compare()) {
    // This is an improvisation on the merge sort algorithm
    // is in-place and works on the divide-and-conquer methodology
    // Choose a pivot and find its appropriate place, such that
    // All elements less than the pivot are on its left and all elements
    // greater are on its right. Once found, split the porlblem into subsets
    // of elements less than and greater than the pivot and recursively
    // follow the process.
    q_sort(array, 0, N-1, comp);

}

int main()
{

    int input[] = {11, 6, 3, 21, 9, 12};
    std::cout << "Before : ";
    for (int i=0; i < 6; i++)
        std::cout << input[i] << " ";
    std::cout << std::endl;

    quick_sort(input, 6);
    // or 
    //quick_sort(input, 6, std::greater<int>());

    std::cout << "After : ";
    for (int i=0; i < 6; i++)
        std::cout << input[i] << " ";
    std::cout << std::endl;

}