Posts Tagged ‘quicksort’

QuickSort Implementation Code in C++

Wednesday, June 25th, 2008

I was having a look at the QuickSort algorithm (as you do for fun) and was trying to find a tidy looking implementation in C++. I found a lot of implementations out there but most of them looked far more complicated than I thought they should have been.

The QuickSort algorithm as printed in the Introduction to Algorithms book looks relatively simple. I wanted a C++ version that has a QuickSort function and a partition function. Many of the implementations that I’ve seen on the internet have both functions merged into one.

The neatest looking QuickSort code that I found was one this Java version written by a Prof. Dr. H. W. Lang. Compare how short and easy to read this piece of code is to other QuickSort implementations. This is close to what I want but the partition part is rolled into the main QuickSort code.

It also had quite a few differences to the Introduction to Algorithms QuickSort. I used the Prof. Dr. H. W. Lang code as a base, split the partition part out, and then made a few other changes to make the implementation closer to the Introduction to Algorithms version. This is what I ended up with.

int partition(int a[], int left, int right, int pivotIndex)
{
    int pivot = a[pivotIndex];
    do
    {
        while (a[left] < pivot) left++;
        while (a[right] > pivot) right--;
        if (left < right && a[left] != a[right])
        {
            swap(a[left], a[right]);
        }
        else
        {
            return right;
        }
    }
    while (left < right);
    return right;
}
void quicksort(int a[], int left, int right)
{
    if (left < right)
    {
        int pivot = (left + right) / 2; // middle
        int pivotNew = partition(a, left, right, pivot);
        quicksort(a, left, pivotNew - 1);
        quicksort(a, pivotNew + 1, right);
    }
}

I tested this in the free Microsoft Visual C++ Express Edition. Here is what I used to test the QuickSort code.

#include "stdafx.h"
#include <iostream>
using namespace std;
void printArray(int thearray[], int count)
{
    for (int i=0; i<count; ++i)
    {
        cout << thearray[i] << " ";
    }
    cout << endl;
}
void arraySortingTests()
{
// unique unsorted
int numbers1[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 10};
int numbers2[] = {19, 16, 10, 12, 14, 17, 13, 18, 15, 11};
// already sorted
int numbers3[] = {10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
// reverse sorted
int numbers4[] = {19, 18, 17, 16, 15, 14, 13, 12, 11, 10};
// all duplicates
int numbers5[] = {7, 7, 7, 7, 7};
// 1 pair
int numbers6[] = {14, 17, 11, 13, 19, 16, 12, 15, 18, 14};
// 1 pair at start
int numbers7[] = {14, 14, 17, 11, 13, 19, 16, 12, 15, 18};
// multiple duplicates
int numbers8[] = {14, 14, 14, 13, 13, 13, 13, 12, 12, 12};
int numbers9[] = {12};
int numbers10[] = {12,10};
quicksort(numbers1, 0, 9);
printArray(numbers1, 10);
quicksort(numbers2, 0, 9);
printArray(numbers2, 10);
quicksort(numbers3, 0, 9);
printArray(numbers3, 10);
quicksort(numbers4, 0, 9);
printArray(numbers4, 10);
quicksort(numbers5, 0, 4);
printArray(numbers5, 5);
quicksort(numbers6, 0, 9);
printArray(numbers6, 10);
quicksort(numbers7, 0, 9);
printArray(numbers7, 10);
quicksort(numbers8, 0, 9);
printArray(numbers8, 10);
quicksort(numbers9, 0, 0);
printArray(numbers9, 1);
quicksort(numbers10, 0, 1);
printArray(numbers10, 2);
}
int _tmain(int argc, _TCHAR* argv[])
{
    arraySortingTests();
    return 0;
}

Update: 25/09/2011 as people noticed my original version of the Quick Sort algorithm didn’t work with duplicates. This new version does, and has extra tests cases to verify this. I’ve had to delete the comments which refer to the old version of the code, as they don’t make sense any more! If you spot any problems with this new version of the code, please let me know.
Update: 30/09/2011 Sergiy in the comments below has found a test case that this doesn’t work with :( If anyone can spot the fix please leave a comment.