Source of 16.18.java

Structures and functions

  1: /** Sorts an array into ascending order. Uses quick sort with
  2:     median-of-three pivot selection for arrays of at least 
  3:     MIN_SIZE entries, and uses insertion sort for other arrays.
  4:     @author Frank M. Carrano
  5:     @author Timothy M. Henry
  6:     @version 5.0
  7: */
  8: public static <T extends Comparable<? super T>>
  9:        void quickSort(T[] a, int first, int last)
 10: {
 11:    if (last - first + 1 < MIN_SIZE)
 12:    {
 13:       insertionSort(a, first, last);
 14:    }
 15:    else
 16:    {
 17:       // Create the partition: Smaller | Pivot | Larger
 18:       int pivotIndex = partition(a, first, last);

 20:       // Sort subarrays Smaller and Larger
 21:       quickSort(a, first, pivotIndex - 1);
 22:       quickSort(a, pivotIndex + 1, last);
 23:    } // end if
 24: } // end quickSort