Java Reference
In-Depth Information
an average cost of O(n
2
). Thus, as n grows, the fraction of inputs with high cost
must be going toward a limit of zero. We can conclude that Quicksort will have
good behavior if we can avoid those very few bad input permutations.
The running time for Quicksort can be improved (by a constant factor), and
much study has gone into optimizing this algorithm. The most obvious place for
improvement is the
findpivot
function. Quicksort's worst case arises when the
pivot does a poor job of splitting the array into equal size subarrays. If we are
willing to do more work searching for a better pivot, the effects of a bad pivot can
be decreased or even eliminated. One good choice is to use the “median of three”
algorithm, which uses as a pivot the middle of three randomly selected values.
Using a random number generator to choose the positions is relatively expensive,
so a common compromise is to look at the first, middle, and last positions of the
current subarray. However, our simple
findpivot
function that takes the middle
value as its pivot has the virtue of making it highly unlikely to get a bad input by
chance, and it is quite cheap to implement. This is in sharp contrast to selecting
the first or last element as the pivot, which would yield bad performance for many
permutations that are nearly sorted or nearly reverse sorted.
A significant improvement can be gained by recognizing that Quicksort is rel-
atively slow when n is small. This might not seem to be relevant if most of the
time we sort large arrays, nor should it matter how long Quicksort takes in the
rare instance when a small array is sorted because it will be fast anyway. But you
should notice that Quicksort itself sorts many, many small arrays! This happens as
a natural by-product of the divide and conquer approach.
A simple improvement might then be to replace Quicksort with a faster sort
for small numbers, say Insertion Sort or Selection Sort. However, there is an even
better — and still simpler — optimization. When Quicksort partitions are below
a certain size, do nothing! The values within that partition will be out of order.
However, we do know that all values in the array to the left of the partition are
smaller than all values in the partition. All values in the array to the right of the
partition are greater than all values in the partition. Thus, even if Quicksort only
gets the values to “nearly” the right locations, the array will be close to sorted. This
is an ideal situation in which to take advantage of the best-case performance of
Insertion Sort. The final step is a single call to Insertion Sort to process the entire
array, putting the elements into final sorted order. Empirical testing shows that
the subarrays should be left unordered whenever they get down to nine or fewer
elements.
The last speedup to be considered reduces the cost of making recursive calls.
Quicksort is inherently recursive, because each Quicksort operation must sort two
sublists. Thus, there is no simple way to turn Quicksort into an iterative algorithm.
However, Quicksort can be implemented using a stack to imitate recursion, as the
amount of information that must be stored is small. We need not store copies of a
