Java Reference
In-Depth Information
Figure15.5
A method for finding a pivot for partitioning a list that guarantees
at least a fixed fraction of the list will be in each partition. We divide the list into
groups of five elements, and find the median for each group. We then recursively
find the median of these n=5 medians. The median of five elements is guaran-
teed to have at least two in each partition. The median of three medians from
a collection of 15 elements is guaranteed to have at least five elements in each
partition.
simply solve by finding the ith best element in the left partition. If the pivot is at
position k < i, then we wish to find the ikth element in the right partition.
What is the worst case cost of this algorithm? As with Quicksort, we get bad
performance if the pivot is the first or last element in the array. This would lead to
possibly O(n
2
) performance. However, if the pivot were to always cut the array in
half, then our cost would be modeled by the recurrence T(n) = T(n=2) +n = 2n
or O(n) cost.
Finding the average cost requires us to use a recurrence with full history, similar
to the one we used to model the cost of Quicksort. If we do this, we will find that
T(n) is in O(n) in the average case.
Is it possible to modify our algorithm to get worst-case linear time? To do
this, we need to pick a pivot that is guaranteed to discard a fixed fraction of the
elements. We cannot just choose a pivot at random, because doing so will not meet
this guarantee. The ideal situation would be if we could pick the median value for
the pivot each time. But that is essentially the same problem that we are trying to
solve to begin with.
Notice, however, that if we choose any constant c, and then if we pick the
median from a sample of size n=c, then we can guarantee that we will discard
at least n=2c elements. Actually, we can do better than this by selecting small
subsets of a constant size (so we can find the median of each in constant time), and
then taking the median of these medians.
Figure 15.5 illustrates this idea.
This
observation leads directly to the following algorithm.
• Choose the n=5 medians for groups of five elements from the list. Choosing
the median of five items can be done in constant time.
• Recursively, select M, the median of the n=5 medians-of-fives.
• Partition the list into those elements larger and smaller than M.
