Java Reference
In-Depth Information
Notice that both the search from the left and the search from the right stop when they encounter
an entry that equals the pivot. This means that rather than leaving such entries in place, they are
swapped. It also means that such an entry has a chance of landing in each of the subarrays.
9.14
Pivot selection.
Ideally, the pivot should be the median value in the array, so that the subarrays
Smaller
and
Larger
each have the same—or nearly the same—number of entries. One way to find the
median value is to sort the array and then get the value in the middle. But sorting the array is the orig-
inal problem, so this circular logic is doomed. Other ways to find the median are too slow to use.
FIGURE 9-6
A partitioning strategy for quick sort
(a)
3
5
0
4
6
1
2
4
0
1
2
3
4
5
6
7
Pivot
(b)
indexFromLeft
1
6
indexFromRight
3
5
0
4
6
1
2
4
0
1
2
3
4
5
6
7
(c)
indexFromLeft
1
2
0
4
1
4
6
indexFromRight
3
6
5
0
1
2
3
4
5
6
7
(d)
indexFromLeft
3
5
indexFromRight
3
2
0
4
6
1
5
4
0
1
2
3
4
5
6
7
(e)
indexFromLeft
3
5
indexFromRight
1
4
3
2
0
6
5
4
0
1
2
3
4
5
6
7
(f)
indexFromLeft
4
3
indexFromRight
3
2
0
1
6
4
5
4
5
6
7
0
1
2
3
4
(g)
3
2
0
1
6
4
5
4
0
1
2
4
5
6
7
3
(h)
3
2
0
1
4
4
5
6
0
1
2
4
5
6
7
3
Smaller
Pivot
Larger
Since choosing the best pivot takes too much time, we should at least try to avoid a bad pivot.
So instead of finding the median of all values in the array, we will take as our pivot the median of
three entries in the array: the first entry, the middle entry, and the last entry. One way to accomplish
this task is to sort only those three entries and use the middle entry of the three as the pivot.
Figure 9-7 shows an array both before and after its first, middle, and last entries are sorted. The
pivot is the 5. This pivot selection strategy is called
median-of-three pivot selection
.
