Faster Sorting Methods - Data Structures and Abstractions with Java - page 230

// Pivot = a[pivotIndex]
// Larger = a[pivotIndex+1..last]
return pivotIndex;
} // end partition

9.18

The quick sort method. Before completing the Java code for quick sort, we need to think about
small arrays. You have seen that the array should contain at least four entries before you call the
partition method. But simply agreeing to use quick sort only on large arrays is not enough. The
pseudocode given for quick sort in Segment 9.10 shows that partitioning even a very large array
will eventually lead to a recursive call that involves an array as small as two entries. The code for
quick sort needs to screen out these small arrays and use another way to sort them. An insertion sort
is a good choice for small arrays. In fact, using it instead of quick sort on arrays of as many as ten
entries is reasonable. The following method implements quick sort with these observations in mind.
The method assumes a constant MIN_SIZE that specifies the size of the smallest array on which we
will use a quick sort.

/** Sorts an array into ascending order. Uses quick sort with
median-of-three pivot selection for arrays of at least
MIN_SIZE entries, and uses insertion sort for other arrays. */
public static <T extends Comparable<? super T>>
void quickSort(T[] a, int first, int last)

{

if (last - first + 1 < MIN_SIZE)
{

insertionSort(a, first, last);

}
else
{

// create the partition: Smaller | Pivot | Larger
int pivotIndex = partition(a, first, last);
// sort subarrays Smaller and Larger
quickSort(a, first, pivotIndex - 1);
quickSort(a, pivotIndex + 1, last);
} // end if
} // end quickSort

Question 3 Trace the steps that the method quickSort takes when sorting the following
array into ascending order:96248753. Assume that MIN_SIZE is 4.

Quick Sort in the Java Class Library
9.19

The class Arrays in the package java.util uses a quick sort to sort arrays of primitive types into
ascending order. The method

public static void sort( type [] a)

sorts an entire array a , while the method

public static void sort( type [] a, int first, int after)