Advanced Sorting - Advanced Topics in Java: Core Concepts in Data Structures - page 267

Compare 72 with 53 ; it is bigger, so move on. 8.

Compare 21 with 53 ; it is smaller, so add 1 to lastSmall (making it 6 ) and swap
num[6] , 63 , with 21 .

9.

We have come to the end of the array; swap num[1] and num[lastSmall] ; this moves the
pivot into its final position ( 6 , in this example).

10.

We end up with this:

num

21 12 18 32 46 53 80 98 72 63

1 2 3 4 5 6 7 8 9 10

The division point is denoted by lastSmall ( 6 ).
We can express the method just described as a function partition1 . The function is shown as part of Program P9.3,
which we write to test quicksort and partition1 .

Program P9.3

import java.io.*;
public class QuicksortTest {

public static void main(String[] args) throws IOException {
int[] num = {0, 37, 25, 43, 65, 48, 84, 73, 18, 79, 56, 69, 32};
int n = 12;
quicksort(num, 1, n);
for (int h = 1; h <= n; h++) System.out.printf("%d ", num[h]);
System.out.printf("\n");
}

public static void quicksort(int[] A, int lo, int hi) {
//sorts A[lo] to A[hi] in ascending order
if (lo < hi) {
int dp = partition1(A, lo, hi);
quicksort(A, lo, dp-1);
quicksort(A, dp+1, hi);
}
} //end quicksort

public static int partition1(int[] A, int lo, int hi) {
//partition A[lo] to A[hi] using A[lo] as the pivot
int pivot = A[lo];
int lastSmall = lo;
for (int j = lo + 1; j <= hi; j++)
if (A[j] < pivot) {
++lastSmall;
swap(A, lastSmall, j);
}
//end for
swap(A, lo, lastSmall);
return lastSmall; //return the division point
} //end partition1