/**
   This class implements a version of the
   quicksort algorithm using a partition
   algorithm that does not rely on the
   first element of the array being vacant,
   nor does it guarantee that the chosen
   pivot value is at the split point of
   the partition.

   @author Cay Horstmann
*/
public class QuickSort
{
   public QuickSort(int[] anArray)
   {
      a = anArray;
   }

   /**
      Sorts the array managed by this sorter
   */
   public void sort()
   {
      sort(0, a.length - 1);
   }

   public void sort(int low, int high)
   {
      if (low >= high) return;
      int p = partition(low, high);
      sort(low, p);
      sort(p + 1, high);
   }

   private int partition(int low, int high)
   {
      // First element
      int pivot = a[low];

      // Middle element
      //int middle = (low + high) / 2;
      //int pivot = a[middle];

      int i = low - 1;
      int j = high + 1;
      while (i < j)
      {
         i++; while (a[i] < pivot) i++;
         j--; while (a[j] > pivot) j--;
         if (i < j) swap(i, j);
      }
      return j;
   }

   /**
      Swaps two entries of the array.
      @param i the first position to swap
      @param j the second position to swap
   */
   private void swap(int i, int j)
   {
      int temp = a[i];
      a[i] = a[j];
      a[j] = temp;
   }

   private int[] a;
}