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 look 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.
void quicksort(int a[], int left, int right)
{
if (left < right)
{
int pivot = partition(a, left, right);
quicksort(a, left, pivot-1);
quicksort(a, pivot+1, right);
}
}
int partition(int a[], int left, int right)
{
int pivot = a[left];
while (true)
{
while (a[left] < pivot) left++;
while (a[right] > pivot) right--;
if (left < right)
{
swap(a[left], a[right]);
}
else
{
return right;
}
}
}
|
I tested this in the free Microsoft Visual C++ Express Edition. Here is what I used to test the QuickSort code.
void arraySortingTests()
{
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};
int numbers4[] = {19, 18, 17, 16, 15, 14, 13, 12, 11, 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);
}
void printArray(int thearray[], int count)
{
for (int i=0; i<count; ++i)
{
cout << thearray[i] << " ";
}
cout << endl;
}
|
