Understanding the QuickSort Algorithm

The QuickSort is one of the fastest methods around for sorting an array. There are a few different versions of it floating around, and optimizations to go along with them, but this article will concentrate on what I believe to be the most straightforward and easy-to-understand method.

The file that goes along with this article contains documented code examples for the QuickSort, one written in C and the other in QuickBASIC.


[size="5"]How it Works

The QuickSort is a recursive function that works using a "divide and conquer" method. It chooses one element, called the partition element, then shifts the elements of the array so that everything less than the partition element comes before it in the array, and everything greater than the partition element comes after it. The partition element is then at its permanent place in the array, and QuickSort calls itself twice: once to sort the upper half of the array, and once to sort the bottom half.

A QuickSort function should take two parameters, which we'll call high and low, that represent the upper and lower bounds of the portion of the array to be sorted. It then performs a few checks. First, if high is less than low, QuickSort does nothing. Then, if high and low represent array elements that are right next to each other sequentially, they are compared and swapped if necessary. If neither of these conditions is true, the main body of the function goes to work.

A partition element is chosen. The choice is irrelevant; you can make it whatever you want. In the included code examples, I have chosen it to be the center element, or the closest integer to (high + low) / 2. The partition element is temporarily swapped with the last element of the array segment. Now we set up two 'pointers', which I'll call top and bottom. These are used to keep track of where we are in the array. The bottom pointer is initialized to low, and the top pointer is initialized to (high - 1), since the array element at high is the partition element, and we just want to leave that alone for now.

The pointers are moved in the following manner. First, bottom is incremented until one of two things happens: an array element is encountered which is greater than the partition element, or bottom > top. Second, top is decremented until either an array element is encountered which is less than the partition element, or bottom > top. Once both of the pointers have been moved appropriately, if bottom is still less than top, the elements they point to are swapped. But if bottom is greater than or equal to top, the pointers have met, and the iteration ends. At this point, the partition element is swapped with the location where the bottom pointer ended up. The partition element is now fixed in its final position within the array, since all elements above it are less than it, and all elements below it are greater.

The array is not sorted yet, though; only the partition element has taken its final place. So now, QuickSort calls itself twice. The first call sorts the first half of the array, which is from positions low to (bottom - 1). The second call sorts the last half of the array, which is from positions (bottom + 1) to high. In this manner, the sizes of the partitions passed to QuickSort get less and less, until eventually, every element in the array has been sorted.


[size="5"]Performance

Well, they don't call it a QuickSort for nothing. The QuickSort is an excellent way to get things ordered in a hurry, but there are some cases where other options may be better. This algorithm is best used with large numbers of elements. If all you have is an array of twenty elements, you'll probably be just as happy with something simple like an insertion sort, and that's a lot easier to implement. The other case in which you may want to use another method is when you know that your data are going to be very close to sorted before applying the algorithm. In this case, the insertion sort is also a good way to go.

One thing I should mention for DOS users in particular... recursive functions are a fantastic way to run out of stack space. So don't be surprised if you try to QuickSort 20,000 integers and you come up against a memory problem! This is another time when it would be best to find another sort routine, one that is non-recursive. A shell sort might be a good option here.

This is my first attempt at an article for GameDev.net, so let me know how I'm doing! Send questions, comments, or hate mail to [email="jdfarrell@students.wisc.edu"]jdfarrell@students.wisc.edu[/email].