Java Reference
In-Depth Information
elements and repeats the same search and swap operations until all the elements are searched
in a
while
loop (lines 20-35).
The method returns the new index for the pivot that divides the partial array into two parts if
the pivot has been moved (line 44). Otherwise, it returns the original index for the pivot (line 47).
Figure 23.8 illustrates how to partition an array (5 2 9 3 8 4 0 1 6 7). Choose the first ele-
ment, 5, as the pivot. Initially
low
is the index that points to element 2 and
high
points to ele-
ment 7, as shown in Figure 23.8a. Advance index
low
forward to search for the first element
(9) that is greater than the pivot and move index
high
backward to search for the first element
(1) that is less than or equal to the pivot, as shown in Figure 23.8b. Swap 9 with 1, as shown
in Figure 23.8c. Continue the search and move
low
to point to element 8 and
high
to point
to element 0, as shown in Figure 23.8d. Swap element 8 with 0, as shown in Figure 23.8e.
Continue to move
low
until it passes
high
, as shown in Figure 23.8f. Now all the elements
are examined. Swap the pivot with element 4 at index
high
. The final partition is shown in
Figure 23.8g. The index of the pivot is returned when the method is finished.
partition illustration
partition animation on
Companion Website
pivot
low
high
5
293840167
(a) Initialize pivot, low, and high
pivot
low
high
5
293840167
(b) Search forward and backward
pivot
low
high
5
213840967
(c) 9 is swapped with 1
pivot
low
high
5
213840967
(d) Continue search
pivot
low
high
5
213048967
(e) 8 is swapped with 0
pivot
low
high
5
213048967
(f) When high < low, search is over
pivot
4
213058967
(g) Pivot is in the right place
The index of the pivot is returned
F
IGURE
23.8
The
partition
method returns the index of the pivot after it is put in the cor-
rect place.
To partition an array of
n
elements, it takes
n
comparisons and
n
moves in the worst case.
Thus, the time required for partition is
O(n)
.
In the worst case, the pivot divides the array each time into one big subarray with the other
array empty. The size of the big subarray is one less than the one before divided. The algo-
rithm requires (
n
O
(
n
) partition time
O
(
n
2
) worst-case time
O
(
n
2
) time.
-
1)
+
(
n
-
2)
+
g
+
2
+
1
=
Search WWH ::
Custom Search