SORTING - Introduction to Java Programming: Comprehensive Version - page 872

12 }
13
14

/** Partition the array list[first..last] */

15 public static int partition( int [] list, int first, int last) {

16 int pivot = list[first]; // Choose the first element as the pivot

17 int low = first + 1 ; // Index for forward search

18 int high = last; // Index for backward search

19
20 while (high > low) {

21 // Search forward from left

22 while (low <= high && list[low] <= pivot) forward

23 low++;

24
25 // Search backward from right

26 while (low <= high && list[high] > pivot) backward

27 high--;

28
29 // Swap two elements in the list
30 if (high > low) {
31 int temp = list[high];
32 list[high] = list[low];
33 list[low] = temp;
34 }
35 }
36
37 while (high > first && list[high] >= pivot)
38 high--;
39
40 // Swap pivot with list[high]
41 if (pivot > list[high]) {
42 list[first] = list[high];
43 list[high] = pivot;
44

swap

place pivot
pivot's new index

return high;

45 }
46 else {

47 return first; pivot's original index

48 }
49 }
50
51 /** A test method */
52 public static void main(String[] args) {
53 int [] list = { 2 , 3 , 2 , 5 , 6 , 1 , -2 , 3 , 14 , 12 };
54 quickSort(list);
55 for ( int i = 0 ; i < list.length; i++)
56 System.out.print(list[i] + " " );
57 }
58 }

-2 1 2 2 3 3 5 6 12 14

The partition method (lines 15-49) partitions the array list[first..last] using the
pivot. The first element in the partial array is chosen as the pivot (line 16). Initially low points
to the second element in the partial array (line 17) and high points to the last element in the
partial array (line 18).
Starting from the left, the method searches forward in the array for the first element that is
greater than the pivot (lines 22-23), then searches from the right backward for the first ele-
ment in the array that is less than or equal to the pivot (lines 26-27). It then swaps these two