// file:   Quicksort.java
// author: Robert Keller
// purpose: Define Quicksort algorithm that can be used with arbitrary
//          Objects and a Comparator.


/**
 * Quicksort is a setup for sorting an array of objects using the Quicksort
 * algorithm.  Comparisons are done with an arbitrary Compartor.
 */

class Quicksort
  {
  /**
   * The array of Objects to be sorted.
   */

  private Object a[];


  /**
   * Constructor for the Quicksort setup
   * @param the array of objects to be sorted
   */

  Quicksort(Object array[])
    {
    a = array;
    }


  /**
   * Sort the array in place using the argument comparator
   */

  void sort(java.util.Comparator comp)
    {
    sort(0, a.length-1, comp);
    }


  /**
   *  Sort the array elements at indices from low to high, inclusive.
   */

  void sort(int low, int high, java.util.Comparator comp)
    {
    if( low >= high )
      return;				// basis case, <= 1 element

    Object pivot = a[(low + high)/2];	// select pivot

    // shift elements <= pivot to bottom
    // shift elements >= pivot to top

    int i = low-1;
    int j = high+1;

    for( ; ; )
      {                             // find two elements to exchange
      do { i++; } while( comp.compare(a[i], pivot) < 0 );	// slide i up
      do { j--; } while( comp.compare(a[j], pivot) > 0 );	// slide j down

      if( i >= j ) break;			// if sliders meet or cross

      swap(i, j);                   // swap elements and continue
      }

    sort(low, i-1, comp);     // sort lower half
    sort(j+1, high, comp);    // sort upper half
    }


  /**
   *  swap(i, j) interchanges the values in a[i] and a[j]
   */

  void swap(int i, int j)
    {
    Object temp = a[i];
    a[i] = a[j];
    a[j] = temp;
    }
}