## QuickSort Implementation Code in C++

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

### 9 Responses to “QuickSort Implementation Code in C++”

1. anon says:

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])’.

2. Brook Monroe says:

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

3. reviewmylife says:

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.

```int numbers5[] = {7, 7, 7, 7, 7};
quicksort(numbers5, 0, 4);
printArray(numbers5, 5);```

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

```#include "stdafx.h"
#include
using namespace std;```
4. keltik says:

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?

5. reviewmylife says:

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.

6. Sergiy says:

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;
}

7. guagua says:

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);
}

8. Charlie says:

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

9. Charlie says:

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);
}
}