Java Reference
In-Depth Information
a wrong way
The popular, uninformed choice is to use the first element (i.e., the element in
position low ) as the pivot. This selection is acceptable if the input is random,
but if the input has been presorted or is in reverse order, the pivot provides a
poor partition because it is an extreme element. Moreover, this behavior will
continue recursively. As we demonstrated earlier in the chapter, we would end
up with quadratic running time to do absolutely nothing. Needless to say, that
would be embarrassing. Never use the first element as the pivot.
Another popular alternative is to choose the larger of the first two distinct
keys 3 as the pivot, but this selection has the same bad effects as choosing the
first key. Stay away from any strategy that looks only at some key near the
front or end of the input group.
Picking the pivot is
crucial to good per-
formance. Never
choose the first
element as pivot.
a safe choice
A perfectly reasonable choice for the pivot is the middle element (i.e., the ele-
ment in array cell ( low+high)/2 ). When the input has already been sorted, this
selection gives the perfect pivot in each recursive call. Of course, we could
construct an input sequence that forces quadratic behavior for this strategy
(see Exercise 8.8). However, the chances of randomly running into a case that
took even twice as long as the average case is extremely small.
The middle element
is a reasonable but
passive choice.
median-of-three partitioning
Choosing the middle element as the pivot avoids the degenerate cases that
arise from nonrandom inputs. Note that this is a passive choice, however. That
is, we do not attempt to choose a good pivot. Instead, we merely try to avoid
picking a bad pivot. Median-of-three partitioning is an attempt to pick a better
than average pivot. In median-of-three partitioning, the median of the first,
middle, and last elements is used as the pivot.
The median of a group of N numbers is the th smallest number.
The best choice for the pivot clearly is the median because it guarantees an
even split of the elements. Unfortunately, the median is hard to calculate, which
would slow quicksort considerably. So we want to get a good estimate of the
median without spending too much time doing so. We can obtain such an esti-
mate by sampling —the classic method used in opinion polls. That is, we pick a
subset of these numbers and find their median. The larger the sample, the more
accurate the estimate. However, the larger sample takes longer to evaluate. A
sample size of 3 gives a small improvement in the average running time of
quicksort and also simplifies the resulting partitioning code by eliminating
In median-of-three
partitioning, the
median of the first,
middle, and last
elements is used as
the pivot. This
approach simplifies
the partitioning
stage of quicksort.
N 2
3. In a complex object, the key is usually the part of the object on which the comparison is based.
 
 
Search WWH ::




Custom Search