Java Reference
In-Depth Information
5 all elements in list1 <= pivot and
6 all elements in list2 > pivot;
7 quickSort(list1);
8 quickSort(list2);
9 }
10 }
pivot
sort first part
sort second part
list1
list2
Each partition places the pivot in the right place. The selection of the pivot affects the perfor-
mance of the algorithm. Ideally, the algorithm should choose the pivot that divides the two
parts evenly. For simplicity, assume the first element in the array is chosen as the pivot. (Pro-
gramming Exercise 23.4 proposes an alternative strategy for selecting the pivot.)
Figure 23.7 illustrates how to sort an array (5 2 9 3 8 4 0 1 6 7) using quick sort. Choose the
first element, 5, as the pivot. The array is partitioned into two parts, as shown in Figure 23.7b.
The highlighted pivot is placed in the right place in the array. Apply quick sort on two partial
arrays (4 2 1 3 0) and then (8 9 6 7). The pivot 4 partitions (4 2 1 3 0) into just one partial array
(0 2 1 3), as shown in Figure 23.7c. Apply quick sort on (0 2 1 3). The pivot 0 partitions it into
just one partial array (2 1 3), as shown in Figure 23.7d. Apply quick sort on (2 1 3). The pivot
2 partitions it into (1) and (3), as shown in Figure 23.7e. Apply quick sort on (1). Since the
array contains just one element, no further partition is needed.
how to partition
quick sort illustration
pivot
5
2
9
3
8
4
0
1
6
7
(a) The original array
pivot
pivot
4
2
1
3
0
5
8
9
6
7
(b) The original array is partitioned
pivot
(c) The partial array (4 2 1 3 0) is
partitioned
02134
pivot
(d) The partial array (0 2 1 3) is
partitioned
0213
(e) The partial array (2 1 3) is
partitioned
123
F
IGURE
23.7
The quick sort algorithm is recursively applied to partial arrays.
The quick sort algorithm is implemented in Listing 23.8. There are two overloaded
quickSort
methods in the class. The first method (line 2) is used to sort an array. The second
is a helper method (line 6) that sorts a partial array with a specified range.
L
ISTING
23.8
QuickSort.java
1
public class
QuickSort {
2
public static void
quickSort(
int
[] list) {
3 quickSort(list,
0
, list.length -
1
);
4 }
5
6
public static void
quickSort(
int
[] list,
int
first,
int
last) {
7
if
(last > first) {
8
int
pivotIndex = partition(list, first, last);
9 quickSort(list, first, pivotIndex -
1
);
10 quickSort(list, pivotIndex +
1
, last);
11 }
sort method
helper method
recursive call
Search WWH ::
Custom Search