Mastering Algorithms With C - Kyle Loudon [132]
Returning to the example of sorting a pile of canceled checks by hand, we begin with an unsorted pile that we partition in two. In one pile we place all checks numbered less than or equal to what we think may be the median value, and in the other pile we place the checks greater than this. Once we have the two piles, we divide each of them in the same manner, and we repeat the process until we end up with one check in every pile. At this point, the checks are sorted.
Since quicksort is a divide-and-conquer algorithm, it is helpful to consider it more formally in terms of the three steps common to all divide-and-conquer algorithms:
Divide: partition the data into two partitions around a partition value.
Conquer: sort the two partitions by recursively applying quicksort to them.
Combine: do nothing since the partitions are sorted after the previous step.
Considering its popularity, it may be surprising that the worst case of quicksort is no better than the worst case of insertion sort. However, with a little care we can make the worst case of quicksort so unlikely that we can actually count on the algorithm performing to its average case, which is considerably better. The key to reliably achieving quicksort's average-case performance lies in how we choose the partition value in the divide step.
Quicksort performs badly when we choose partition values that continually force the majority of the elements into one partition. Instead, we need to partition the elements in as balanced a manner as possible. For example, partitioning around 10 in the set {15, 20, 18, 51, 36, 10, 77, 43} results in the unbalanced partitions of {10} and {20, 18, 51, 36, 15, 77, 43}. On the other hand, partitioning around 36 results in the more balanced partitions of {15, 20, 18, 10} and {36, 51, 77, 43}.
One approach that works well in choosing partition values is to select them randomly. Statistically, this prevents any particular set of data from eliciting bad behavior, even if we try to bog down the algorithm intentionally. We can improve partitioning further by randomly choosing three elements and selecting their median as the partition value. This is called the median-of-three method, which virtually guarantees average-case performance. Because this approach to partitioning relies on the statistical properties of random numbers to help the performance of quicksort overall, quicksort is a good example of a randomized algorithm (see Chapter 1).
Interface for Quicksort
Name
qksort
Synopsis
int qksort(void *data, int size, int esize, int i, int k, int (*compare)
(const void *key1, const void *key2));
Return Value
0 if sorting is successful, or -1 otherwise.
Description
Uses quicksort to sort the array of elements in data. The number of elements in data is specified by size. The size of each element is specified by esize. The arguments i and k define the current partition being sorted and initially should be and size - 1, respectively. The function pointer compare specifies a user-defined function to compare elements. It should perform in a manner similar to that described for issort. When qksort returns, data contains the sorted elements.
Complexity
O (n lg n), where n is the number of elements to be sorted.
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