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

Stanger

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

Hogg

Hi, I am trying to understand this algorithm, What is the pivot? If I change the value of p or q, the algorithm doesn't sort all the array. – Leptorrhine

@Leptorrhine A[p] is the pivot element. Since p is the left bound of the part of the array that needs to be sorted, the pivot element is always the first element. Only the part of the array between index p and q gets sorted. – Hogg

So if I wanted to pick another pívot how could I do it? – Leptorrhine

Rewrite the method int partition(...). E.g. select the second(or last) element and swap it with the first at the beginning of the current procedure. – Hogg

why is q=10 ? while p is still = 0. – Pert

@AbhinavGauniyal The array has 10 element and we want to sort it completely. p is the first index in the range and q the first not on the range. Thus the values p=0 and q=10 – Hogg

@Hogg I was taking p and q in different contexts, thanks for explaining :) – Pert

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;

}

Jolo

I guess there is a bug in your implementation. I used your code for an array of random integers. the program just blocked somewhere... – Sniff

Answer 3

A much easier and clean implementation, also gives you number of minimum SWAPS in for QuickSort:

int quickSort(int[], int, int);

int partition(int[], int, int, int&);

int main()
{
    int array[] = {4, 2, 5};
    int size = sizeof(array)/sizeof(array[0]);

    /*
     first and last indices are passed
     idea is to move lower elements to the left of the list/pivot
     */

    int swaps = quickSort(array, 0, size-1);

    std::cout << "Minimum Swaps are: " << swaps << std::endl;

    for(int i = 0; i < size; i++)
    {
        std::cout << array[i] << " ";
    }
}

int quickSort(int array[], int start, int end)
{
    int swaps = 0;
    if(start < end)
    {
        int pIndex = partition(array, start, end, swaps);
        //after each call one number(the PIVOT) will be at its final position
        swaps += quickSort(array, start, pIndex-1);
        swaps += quickSort(array, pIndex+1, end);
    }
    return swaps;
}

int partition(int array[], int start, int end, int& swaps)
{
    int pivot = array[end];
    int pIndex = start;

    for(int i = start; i < end; i++)
    {
        if(array[i] <= pivot)
        {

            if(pIndex != i)
            {
                std::swap(array[i], array[pIndex]);
                swaps++;
            }
            pIndex++;
        }
    }
    if(pIndex != end)
    {
        std::swap(array[pIndex], array[end]);
        swaps++;
    }
    return pIndex;
}

Snippy

Answer 4

Since I see various answers, you could try this:

#include <iostream>

void quickSort(int a[], int first, int last);
int pivot(int a[], int first, int last);
void swap(int& a, int& b);
void swapNoTemp(int& a, int& b);
void print(int array[], const int& N);

using namespace std;

int main()
{
    int test[] = { 7, -13, 1, 3, 10, 5, 2, 4 };
    int N = sizeof(test)/sizeof(int);

    cout << "Size of test array :"  << N << endl;

    cout << "Before sorting : " << endl;
    print(test, N);

    quickSort(test, 0, N-1);

    cout << endl << endl << "After sorting : " << endl;
    print(test, N);

    return 0;
}

/**
 * Quicksort.
 * @param a - The array to be sorted.
 * @param first - The start of the sequence to be sorted.
 * @param last - The end of the sequence to be sorted.
*/
void quickSort( int a[], int first, int last ) 
{
    int pivotElement;

    if(first < last)
    {
        pivotElement = pivot(a, first, last);
        quickSort(a, first, pivotElement-1);
        quickSort(a, pivotElement+1, last);
    }
}

/**
 * Find and return the index of pivot element.
 * @param a - The array.
 * @param first - The start of the sequence.
 * @param last - The end of the sequence.
 * @return - the pivot element
*/
int pivot(int a[], int first, int last) 
{
    int  p = first;
    int pivotElement = a[first];

    for(int i = first+1 ; i <= last ; i++)
    {
        /* If you want to sort the list in the other order, change "<=" to ">" */
        if(a[i] <= pivotElement)
        {
            p++;
            swap(a[i], a[p]);
        }
    }

    swap(a[p], a[first]);

    return p;
}

I have it in Quicksort (C++).

Refulgent