Java Reference
In-Depth Information
Recall that median-of-three partitioning requires that we find the median
of the first, middle, and last elements. The easiest way to do so is to sort them
in the array. The result is shown in Figure 8.20. Note the resulting shading:
The element that winds up in the first position is guaranteed to be smaller than
(or equal to) the pivot, and the element in the last position is guaranteed to be
larger than (or equal to) the pivot. This outcome tells us four things.
Computing the
median-of-three
involves sorting
three elements.
Hence we can give
the partitioning
step a head start
and also never
worry about run-
ning off the end of
the array.
We should not swap the pivot with the element in the last position.
Instead, we should swap it with the element in the next-to-last posi-
tion, as shown in Figure 8.21.
n
We can start
i
at
low+1
and
j
at
high-2
.
n
We are guaranteed that, whenever
i
searches for a large element, it
will stop because in the worst case it will encounter the pivot (and we
stop on equality).
n
We are guaranteed that, whenever
j
searches for a small element, it
will stop because in the worst case it will encounter the first element
(and we stop on equality).
n
All these optimizations are incorporated into the final Java code.
8.6.7
small arrays
Our final optimization concerns small arrays. Is using a high-powered routine
such as quicksort worthwhile when there are only 10 elements to sort? The
answer is of course not. A simple routine, such as the insertion sort, probably
is faster for small arrays. The recursive nature of quicksort tells us that we
Sort 10 or fewer
items by insertion
sort. Place this test
in the recursive
quicksort routine.
figure 8.19
Original array
8
1
4
9
6
3
5
2
7
0
figure 8.20
Result of sorting three
elements (first, middle,
and last)
0
1
4
9
6
3
5
2
7
8
figure 8.21
Result of swapping
the pivot with the
next-to-last element
0
1
4
9
7
3
5
2
6
8
Search WWH ::
Custom Search