package username.sorting;

import java.util.Comparator;
import java.util.Random;
import java.util.Vector;

/**
 * Sort using the legendary Quicksort routine.
 *
 * @author Samuel A. Rebelsky
 * @version 1.0 of May 2005
 */
public class Quicksorter<T>
  implements OutOfPlaceVectorSorter<T>
{
  /**
   * The random number generator used to select the pivot.
   */
  Random rng;

  public Quicksorter()
  {
    this.rng = new Random();
  } // Quicksorter<T>

  public Vector<T> sort(Vector<T> vec, Comparator<T> c)
  {
    int len = vec.size();
    // Quicksort is traditionally an in-place sort, so we 
    // make an exact copy of the vector and then sort it in
    // place.
    Vector<T> copy = new Vector<T>(len);
    for (int i = 0; i < len; i++) {
      copy.add(vec.get(i));
    } // for
    // We use a helper routine that takes lb and ub as parameters
    // to do the real sorting.
    this.sort(copy, 0, len-1, c);
    return copy;
  } // sort(Vector<T>, Comparator<T>)

  /**
   * Sort the subvector of elements between lb and ub inclusive.
   */
  void sort(Vector<T> vec, int lb, int ub, Comparator<T> c)
  {
    // If the subvector has one element or zero elements, we're
    // done.
    if (ub <= lb) return;
    // Pick a pivot and put it at the front of the subvector.
    int pivotPos = pickPivotPos(vec, lb, ub);
    this.swap(vec, lb, pivotPos);
    // Rearrange the vector so that small things are at the left and
    // large things are at the right.
    T pivot = vec.get(lb);
    int left = lb;
    int right = ub;
    while (left < right) {
      // Retreat the left cursor until we hit a small value.
      // Note that we must hit a small value because the value at
      // lb is small.
      while (c.compare(pivot, vec.get(right)) < 0) {
        right--;
      } // while
      // Advance the right cursor until we hit a large value or
      // reach the large cursor.
      while ((left < right) && (c.compare(pivot, vec.get(left)) >= 0)) {
        left++;
      } // while
      // At this point, right is on a small value and either  left
      // is on a large value or left and right are the same place.  
      // In both cases, left <= right.  Hence, we can swap the values at 
      // left and right and get large things on the right and small things 
      // on the left.
      this.swap(vec, left, right);
    } // while
    // At this point, we know that (1) left = right, (2) everything
    // to the left of left is small (including the thing at left), and
    // (3) everything to the right of right is large.  We swap the
    // pivot into this middle position (so that we can be sure that it's
    // where it belongs), and then resort the two halves.
    this.swap(vec, lb, left);
    this.sort(vec, lb, left-1, c);
    this.sort(vec, left+1, ub, c);
  } // sort(Vector<T>, int, int, Comparator<T>)

  int pickPivotPos(Vector<T> vec, int lb, int ub)
  {
    int offset = rng.nextInt(1 + ub - lb);
    return lb + offset;
  } // pickPivotPos(Vector<T>, int, int)

  /**
   * Swap two values in a vector.
   *
   * @pre
   *   0 <= a,b < vec.size()
   * @post
   *   vec.get(a) = "old value of" vec.get(b)
   * @post
   *   vec.get(b) = "old value of" vec.get(a)
   */
  void swap(Vector<T> vec, int a, int b)
  {
    T tmp = vec.get(a);
    vec.set(a, vec.get(b));
    vec.set(b, tmp);
  } // swap(Vector<T>, int, int)

} // class Quicksorter