Java Reference
In-Depth Information
FIGURE 9-7
Median-of-three pivot selection: (a) The original array; (b) the
array with its first, middle, and last entries sorted
(a)
5
6
9
3
7
1
8
4
2
(b)
2
8
6
4
5
3
7
1
9
Pivot
Note:
Median-of-three pivot selection avoids worst-case performance by quick sort when
the given array is already sorted or nearly sorted. While it theoretically does not avoid worst-
case performance for other arrays, such performance is unlikely in practice.
9.15
Adjusting the partition algorithm.
Median-of-three pivot selection suggests some minor adjust-
ments to our partitioning scheme. Previously, we swapped the pivot with the last entry in the array
prior to partitioning. But here, the first, middle, and last entries in the array are sorted, so we know
that the last entry is at least as large as the pivot. Thus, the last entry belongs in the subarray
Larger
.
We can simply leave the last entry in place. To get the pivot out of the way, we can swap it with the
next-to-last entry,
a[last
-
1]
,
as Figure 9-8 shows. Thus, the partition algorithm can begin its
search from the right at index
last
-
2
.
FIGURE 9-8
(a) The array with its first, middle, and last entries sorted;
(b) the array after positioning the pivot and just before partitioning
(a)
2
8
6
4
5
3
7
1
9
Pivot
(b)
2
8
6
4
1
3
7
5
9
Pivot
indexFromRight
indexFromLeft
Also notice that the first entry is at least as small as the pivot, and so it belongs in the subarray
Smaller
.
Thus, we can leave the first entry in place and have the partition algorithm begin its search from the left at
index
first + 1
. Figure 9-8b shows the status of the array at this point, just prior to partitioning.
This scheme provides a side benefit that simplifies the loops for the two searches. The search from
the left looks for an entry that is greater than or equal to the pivot. That search will terminate because, at
worst, it will stop at the pivot. The search from the right looks for an entry that is less than or equal to the
pivot. That search will terminate because, at worst, it will stop at the first entry. Thus, the loops need not
do anything special to prevent the searches from going beyond the ends of the array.
After the search loops end, we need to position the pivot between the subarrays
Smaller
and
Larger
. We do this by swapping the entries
a[indexFromLeft]
and
a[last
-
1]
.
