Java Reference
In-Depth Information
This ideal situation might not always occur, however. In the worst case, each partition has one empty
subarray. Although one recursive call will have nothing to do, the other call must sort
n
-
1 entries instead
of
n
/
2. The result is
n
levels of recursive calls instead of log
n
. Thus, in the worst case, quick sort is O(
n
2
).
The choice of pivots, then, affects quick sort's efficiency. Some pivot-selection schemes can
lead to worst-case behavior if the array is already sorted or nearly sorted. In practice, nearly sorted
arrays can occur more frequently than you might imagine. As you will see later, our pivot-selection
scheme will avoid worst-case behavior for sorted arrays.
Although we will not prove it, quick sort is O(
n
log
n
) in the average case. While merge sort is
always O(
n
log
n
), quick sort can be faster than merge sort in practice and does not require the additional
memory that merge sort needs for merging.
Note:
The time efficiency of quick sort
Quick sort is O(
n
log
n
) in the average case but O(
n
2
) in the worst case. The choice of pivots
affects its behavior.
Various strategies are possible for choosing a pivot and for creating the partition in Figure 9-5. For
now, we will assume that you have chosen a pivot, and so we will describe how to create a partition
independently of your pivot-selection strategy. Later, our actual pivot-selection scheme will sug-
gest minor changes to this partitioning process.
After choosing a pivot, swap it with the last entry in the array so that the pivot is not in your way
while you create the partition. Figure 9-6a shows an array after this step. Starting at the beginning of the
array and moving toward the end (left to right in the figure), look for the first entry that is greater than or
equal to the pivot. In Figure 9-6b, that entry is 5 and occurs at the index
indexFromLeft
. In a similar
fashion, starting at the next-to-last entry and moving toward the beginning of the array (right to left in the
figure), look for the first entry that is less than or equal to the pivot. In Figure 9-6b, that entry is 2 and
occurs at the index
indexFromRight
. Now, if
indexFromLeft
is less than
indexFromRight
, swap the
two entries at those indices. Figure 9-6c shows the result of this step. The 2, which is less than the pivot,
has moved toward the beginning of the array while the 5, which is greater than the pivot, has moved in
the opposite direction.
Continue the searches from the left and from the right. Figure 9-6d shows that the search from the left
stops at 4 and the search from the right stops at 1. Since
indexFromLeft
is less than
indexFromRight
,
swap 4 and 1. The array now appears as in Figure 9-6e. Entries equal to the pivot are allowed in either piece
of the partition.
Continue the searches again. Figure 9-6f shows that the search from the left stops at 6 while the search
from the right goes beyond the 6 to stop at 1. Since
indexFromLeft
is not less than
indexFromRight
, no
swap is necessary and the searches end. The only remaining step is to place the pivot between the subarrays
Smaller
and
Larger
by swapping
a[indexFromLeft]
and
a[last]
, as Figure 9-6g shows. The com-
pleted partition appears in Figure 9-6h.
Note that the previous searches must not go beyond the ends of the array. Soon, in Segment 9.15,
you will see a convenient way to implement this requirement.
9.13
Entries equal to the pivot.
Notice that both of the subarrays
Smaller
and
Larger
can contain
entries equal to the pivot. This might seem a bit strange to you. Why not always place any entries
that equal the pivot into the same subarray? Such a strategy would tend to make one subarray larger
than the other. However, to enhance quick sort's performance, we want the subarrays to be as
nearly equal in size as possible.
