Java Reference
In-Depth Information
some special cases. Large sample sizes do not significantly improve perfor-
mance and thus are not worth using.
The three elements used in the sample are the first, middle, and last ele-
ments. For instance, with input 8, 1, 4, 9, 6, 3, 5, 2, 7, 0, the leftmost element
is 8, the rightmost element is 0, and the center element is 6; thus the pivot
would be 6. Note that for already sorted items, we keep the middle element as
the pivot, and in this case, the pivot is the median.
8.6.4 a partitioning strategy
There are several commonly used partitioning strategies. The one that we
describe in this section gives good results. The simplest partitioning strategy
consists of three steps. In Section 8.6.6 we show the improvements that occur
when median-of-three pivot selection is used.
The first step in the partitioning algorithm is to get the pivot element out
of the way by swapping it with the last element. The result for our sample
input is shown in Figure 8.12. The pivot element is shown in the darkest shade
at the end of the array.
For now we assume that all the elements are distinct and leave for later
what to do in the presence of duplicates. As a limiting case, our algorithm
must work properly when all the elements are identical.
Step 1: Swap the
pivot with the ele-
ment at the end.
In step 2, we use our partitioning strategy to move all the small elements
to the left in the array and all the large elements to the right. Small and large
are relative to the pivot. In Figures 8.12-8.17, white cells are those that we
know are correctly placed. The lightly shaded cells are not necessarily cor-
rectly placed.
We search from left to right, looking for a large element, using a counter
i , initialized at position low . We also search from right to left, looking for a
small element, using a counter j , initialized to start at high-1 . Figure 8.13
shows that the search for a large element stops at 8 and the search for a small
element stops at 2. These cells have been lightly shaded. Note that, by skip-
ping past 7, we know that 7 is not small and thus is correctly placed. Thus it is
Step 2: Run i from
left to right and j
from right to left.
When i encoun-
ters a large ele-
ment, i stops.
When j encoun-
ters a small ele-
ment, j stops. If i
and j have not
crossed, swap their
items and con-
tinue. Otherwise,
stop this loop.
figure 8.12
Partitioning algorithm:
Pivot element 6 is
placed at the end.
8
1
4
9
0
3
5
2
7
6
figure 8.13
Partitioning algorithm:
i stops at large
element 8; j stops at
small element 2.
8
1
4
9
0
3
5
2
7
6
 
Search WWH ::




Custom Search