QuickSorter.java.html

  1  /**
  2     The sort method of this class sorts an array, using the quick 
  3     sort algorithm.
  4  */
  5  public class QuickSorter
  6  {
  7     /**
  8        Sorts an array, using quick sort.
  9        @param a the array to sort
 10     */
 11     public static void sort(int[] a)
 12     {  
 13        sort(a, 0, a.length - 1);
 14     }
 15  
 16     /**
 17        Sorts a portion of an array, using quick sort.
 18        @param a the array to sort
 19        @param from the first index of the portion to be sorted
 20        @param to the last index of the portion to be sorted
 21     */
 22     public static void sort(int[] a, int from, int to)
 23     {
 24        if (from >= to) { return; }
 25        int p = partition(a, from, to);
 26        sort(a, from, p);
 27        sort(a, p + 1, to);
 28     }
 29  
 30     /**
 31        Partitions a portion of an array.
 32        @param a the array to partition
 33        @param from the first index of the portion to be partitioned
 34        @param to the last index of the portion to be partitioned
 35        @return the last index of the first partition
 36     */
 37     private static int partition(int[] a, int from, int to)
 38     {
 39        int pivot = a[from];
 40        int i = from - 1;
 41        int j = to + 1;
 42        while (i < j)
 43        {
 44           i++; while (a[i] < pivot) { i++; }
 45           j--; while (a[j] > pivot) { j--; }
 46           if (i < j) { ArrayUtil.swap(a, i, j); }
 47        }
 48        return j;
 49     }
 50  }