Quicksort Algorithm

9-May-2003

I recently came upon the need for a sorting algorithm that did not depend on the qsort function from the C runtime library. After doing some research about various sorting methods, I set out to write my own implementation of the famous quicksort algorithm.

After four hours of straining my brain and stressing about squeezing every last bit of performance out of my code, I had a function that was able to sort an array of integers. It was a simple exercise to adapt this function to my List templated container class so that it could be used to sort a list with elements of any data type.

When I started benchmarking this algorithm, I was shocked by the results. On random data, it operates twice as quickly as the CRT qsort, and on already sorted data it's about four times as fast. In the course of my researching, I found another quicksort routine that "evildave" posted on SourceForge, so I added it to my benchmark program as well.

I compiled my benchmark program with Microsoft Visual Studio .NET 2002 using the "Maximize Speed" compiler optimization. Here are the results of my benchmarks:

Populating array 1 with random integers...
Duplicating array 1 to array 2...
Duplicating array 1 to array 3...

Sorting array 1 with qsort...
Time: 142728

Sorting array 2 with my_qsort...
Time: 71118

Sorting array 3 with their_qsort...
Time: 60411


Populating array 1 with sequential ascending integers...
Duplicating array 1 to array 2...
Duplicating array 1 to array 3...

Sorting array 1 with qsort...
Time: 68272

Sorting array 2 with my_qsort...
Time: 15724

Sorting array 3 with their_qsort...
Time: 28497041


Populating array 1 with sequential descending integers...
Duplicating array 1 to array 2...
Duplicating array 1 to array 3...

Sorting array 1 with qsort...
Time: 71652

Sorting array 2 with my_qsort...
Time: 18576

Sorting array 3 with their_qsort...
Time: 28068851

While my quicksort algorithm is very slightly slower than evildave's algorithm when operating on random data, it is on the order of 1000 times faster when operating on data that is already sorted, the pathological worst-case scenario for the traditional quicksort. Additionally, it is between two and four times faster than the CRT library's qsort.

You can download the source code for my benchmark here. This code includes a function called my_qsort, which is the algorithm I wrote, as well as a function called their_qsort, which is evildave's algorithm that I found on SourceForge.

If you like what I am doing, donate a dollar or two.

This site is hosted by DreamHost Web Hosting.