Mastering Algorithms with C

Implementation and Analysis of Quicksort

Quicksort works fundamentally by recursively partitioning an unsorted set of elements until all partitions contain a single element. In the implementation presented here, data initially contains the unsorted set of size elements stored in a single block of contiguous storage. Quicksort sorts in place, so all partitioning is performed in data as well. When qksort returns, data is completely sorted.

As we have seen, an important part of quicksort is how we partition the data. This task is performed in the function partition (see Example 12.2) . This function partitions the elements between positions i and k in data, where i is less than k.

We begin by selecting a partition value using the median-of-three method mentioned earlier. Once the partition value has been selected, we move from k to the left in data until we find an element that is less than or equal to it. This element belongs in the left partition. Next, we move from i to the right until we find an element that is greater than or equal to the partition value. This element belongs in the right partition. Once two elements are found in the wrong partition, they are swapped. We continue in this way until i and k cross. (You may want to consider how we know that if any one element is in the wrong partition, there is always one that can be swapped with it.) Once i and k cross, all elements to the left of the partition value are less than or equal to it, and all elements to the right are ...