Java Reference
In-Depth Information
a white cell. Now, we have a large element, 8, on the left-hand side of the
array and a small element, 2, on the right-hand side of the array. We must
swap these two elements to place them correctly, as shown in Figure 8.14.
As the algorithm continues,
i
stops at large element 9 and
j
stops at small
element 5. Once again, elements that
i
and
j
skip during the scan are guaran-
teed to be correctly placed. Figure 8.15 shows the result: The ends of the array
(not counting the pivot) are filled with correctly placed elements.
Next, swap the elements that
i
and
j
are indexing, as shown in Figure 8.16.
The scan continues, with
i
stopping at large element 9 and
j
stopping at
small element 3. However, at this point
i
and
j
have crossed positions in the
array. Consequently, a swap would be useless. Hence Figure 8.17 shows that
the item being accessed by
j
is already correctly placed and should not
move.
Figure 8.17 shows that all but two items are correctly placed. Wouldn't it
be nice if we could just swap them and be done? Well, we can. All we need to
do is swap the element in position
i
and the element in the last cell (the pivot),
as shown in Figure 8.18. The element that
i
is indexing clearly is large, so
moving it to the last position is fine.
Step 3: Swap the
element in position
i
with the pivot.
figure 8.14
Partitioning algorithm:
The out-of-order
elements 8 and 2 are
swapped.
2
1
4
9
0
3
5
8
7
6
figure 8.15
Partitioning algorithm:
i
stops at large
element 9;
j
stops at
small element 5.
2
1
4
9
0
3
5
8
7
6
figure 8.16
Partitioning algorithm:
The out-of-order
elements 9 and 5 are
swapped.
2
1
4
5
0
3
9
8
7
6
figure 8.17
Partitioning algorithm:
i
stops at large
element 9;
j
stops at
small element 3.
2
1
4
5
0
3
9
8
7
6
figure 8.18
Partitioning algorithm:
Swap pivot and
element in position
i
.
2
1
4
5
0
3
6
8
7
9
Search WWH ::
Custom Search