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 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 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.

This quicksort algorithm will not work for an array with all the same numbers – an infinite loop ocurrs. To remove the infinte loop, change ‘if (left < right)’ to ‘if (left < right && a[left] != a[right])’.

Does that correction go into quicksort() or partition()?

Hi Brook – it goes in the partition function – I’ve now fixed the Quick Sort code in the post.

Here’s the test code for all the values being the same.

And in case anyone is having trouble setting this up in Visual Studio here are the includes you need:

Doesn’T work because, I don’t have anything like a swap function? Is it in some of the standard libraries that cygwin is equipped with?

Hi keltik, the code hasn’t been tested on cygwin – I’m not sure if cygwin has a suitable swap function built in, but it should only take a few lines of code to write your own version. You just need to swap the numbers at the memory addresses passed in to the function.

Won’t work on the following input:

{14, 19, 11, 20, 19, 16, 12, 19, 20, 21}

Returns:

11 12 14 16 19 19 20 19 20 21

which is not sorted. For people who still need swap function – I wrote it:

void swap(int & a, int & b)

{

int c = a;

a = b;

b = c;

}

Try this site for a java algorithm similar to your c++ algorithm but which may work in all circumstances.

http://www.algolist.net/Algorithms/Sorting/Quicksort

int arr[] = { 3,5,8,2,5,7,3,1,7,3};

try this case, code is wrong.

if (left < right && a[left] != a[right])

{

swap(a[left], a[right]);

}

else

{

return right;

}

should be

if (left < right)

{

if(a[left] != a[right])

swap(a[left], a[right]);

}

else

{

return right;

}

or else we are not returning the pivot at correct location.

One more thing, if correct it in the way above

while (a[left] pivot) right–;

should be

while (a[left] = pivot) right–;

suppose a[left]==a[right]==pivot

infinite loop

regards.

won’t work for {3,6,8,6}

fix

void quickSort(int arr[], int left, int right)

{

if (left >= right) return;

int l = left, r = right;

int pivot = arr[(left + right)>>1];

while (l <= r) {

while (arr[l] pivot) r–;

if (l <= r) {

int temp = arr[l];

arr[l] = arr[r];

arr[r] = temp;

l++;

r–;

}

}

quickSort(arr, left, r);

quickSort(arr, l, right);

}

{5,6,5} not working if pivot index =0

int part(int a[], int lo, int hi)

{

int p = a[lo]; //pivot fixed

int i = lo;

int j = hi;

if ((hi – lo) <= 0) return lo;

while (i<j)

{

while (a[i]<p && ij)

{

//p is the biggest

–i;

swap(a[lo], a[i]);

–i;

return i;

}

if (i == j)

{

return i;

}

while (a[j] > p && j >= i) –j;

if (j <= i)

{

//p is the smallest

return i;

}

if (i= p && a[j] = a[j] is always true

if (a[j] == p)

{

if (a[i] == p)

{

++i;

}

else

{

//a[i] > p is true

swap(a[i], a[j]);

–j;

}

}

else // a[j] =p && a[j] p && a[j] < p

swap(a[i], a[j]);

++i;

–j;

}

}

if (i < j) continue;

else if (i == j)

{

if (a[i] p ) { swap(a[i], a[i + 1]); return i; }

}

}//if (i<j)

}//while (i<j)

return i;

}

void mysort(int a[], int low, int hi)

{

int x;

if (low<hi)

{

x = part(a, low, hi);

if (lowx)

mysort(a, x+1, hi);

}

}