/*
 *  This code is from the book:
 *
 *    Winder, R and Roberts, G (2000) Developing Java
 *    Software, second edition, John Wiley & Sons.
 *
 *  It is copyright (c) 2000 Russel Winder and Graham Roberts.
 */

package ADS ;
/**
 *  Sort an array of <CODE>Object</CODE>s using Quicksort.  This is an
 *  O(n.log(n)) sort except when the data is almost sorted in which
 *  case it O(n^2).
 *
 *  @version 1.1 1999.11.27
 *  @author Russel Winder
 */
public class Quicksort {
  /**
   *  The sort operation.
   *
   *  @param a the array to be sorted.
   *  @param c the <CODE>Comparator</CODE> used to compare the
   *  <CODE>Object</CODE>s during the sort process.
   */ 
  public static void sort(final Object[] a, final Comparator c) {
    quicksort(a, 0, a.length-1, c) ;
  }
  /**
   *  Given the array and two indices, swap the two items in the
   *  array.
   */
  private static void swap(final Object[] a,
                           final int x,
                           final int y) {
    Object temp = a[x] ;
    a[x] = a[y] ;
    a[y] = temp ;
  }
  /**
   *  Partition an array in two using the pivot value that is at the
   *  centre of the array being partitioned.
   *
   *  <P> This partition implementation based on that in Winder, R
   *  (1993) "Developing C++ Software", Wiley, p.395.  NB. This
   *  implementation (unlike most others) does not guarantee that
   *  the split point contains the pivot value.  Unlike other
   *  implementations, it requires only < (or >) relation and not
   *  both < and <= (or > and >=).  Also, it seems easier to program
   *  and to comprehend.
   *
   *  @param a the array out of which to take a slice.
   *  @param lower the lower bound of this slice.
   *  @param upper the upper bound of this slice.
   *  @param c the <CODE>Comparator</CODE> to be used to define the
   *  order.
   */
  private static int partition(final Object[] a,
                               int lower,
                               int upper,
                               final Comparator c) {
    Object pivotValue = a[(upper+lower+1)/2] ;
    while (lower <= upper) {
      while (c.relation(a[lower], pivotValue)) {
        lower++ ;
      }
      while (c.relation(pivotValue, a[upper])) {
        upper-- ;
      }
      if (lower <= upper) {
        if (lower < upper) {
          swap(a, lower, upper) ;
        }
        lower++ ;
        upper-- ;
      }
    }
    return upper ;
  }
  /**
   *  The recursive Quicksort function.
   *
   *  @param a the array out of which to take a slice.
   *  @param lower the lower bound of this slice.
   *  @param upper the upper bound of this slice.
   *  @param c the <CODE>Comparator</CODE> to be used to define the
   *  order.
   */
  private static void quicksort(final Object[] a,
                                final int lower,
                                final int upper,
                                final Comparator c) {
    int sliceLength = upper-lower+1 ;
    if (sliceLength > 1) {
      if (sliceLength == 2) {
        if (c.relation(a[upper], a[lower])) {
          swap (a, lower, upper) ;
        }
      } else {
        //  This partition implementation does not guarantee that the
        //  split point contains the pivot value so we cannot assume
        //  that the pivot is between the two slices.
        int pivotIndex = partition(a, lower, upper, c) ;
        quicksort(a, lower, pivotIndex, c) ;
        quicksort(a, pivotIndex+1, upper, c) ;
      }
    }
  }
}