package example.sort;

public final class Quicksort {

  /**
   * Sort the given array, calling the recursive sort method..
   * 
   * @param array
   *          the array we are sorting
   */
  public static <T extends Comparable<T>> void sort(T[] array) {
    recursiveSort(array, 0, array.length - 1);
  }

  /**
   * Recursive sort function for quicksort.
   * 
   * @param array
   *          the array we are sorting
   * @param left
   *          the left bound of the sublist of the array we are sorting
   * @param right
   *          the right bound of the sublist of the array we are sorting
   */
  private static <T extends Comparable<T>> void recursiveSort(T[] array, int left, int right) {
    if (left == right) {
      // already sorted
      return;
    }
    // check that our left and right bounds haven't crossed over each other
    if (left < right) {
      // partition the array around the pivot
      int pivotIdx = partition(array, left, right, selectInitialPivotIndex(array, left, right));
      // recursively sort the left and right sublists
      recursiveSort(array, left, pivotIdx - 1);
      recursiveSort(array, pivotIdx + 1, right);
    }
  }

  /**
   * Select the initial pivot index. Uses median of 3 method.
   * 
   * @param array
   *          the array from which to select a pivot index
   * @param left
   *          the left bound of the sublist of the array we are sorting
   * @param right
   *          the right bound of the sublist of the array we are sorting
   * @return the initial pivot index
   */
  private static <T extends Comparable<T>> int selectInitialPivotIndex(T[] array, int left, int right) {
    int center = (left + right) / 2;
    // order left & center
    if (array[left].compareTo(array[center]) > 0) {
      swap(array, left, center);
    }
    // order left & right
    if (array[left].compareTo(array[right]) > 0) {
      swap(array, left, right);
    }
    // order center & right
    if (array[center].compareTo(array[right]) > 0) {
      swap(array, center, right);
    }
    // use the center (median)
    return center;
  }

  /**
   * Partition the array into L v R, where v is the pivot value, L is a sublist
   * of values in the array that are less than or equal to v, and R is a sublist
   * of values of the array that are greater than or equal to v.
   * 
   * @param array
   *          the array to partition
   * @param left
   *          the left bound of the sublist of the array we are sorting
   * @param right
   *          the right bound of the sublist of the array we are sorting
   * @param pivotIdx
   *          the index of the pivot value, v
   * @return
   */
  private static <T extends Comparable<T>> int partition(T[] array, int left, int right, int pivotIdx) {
    // since we used the median of 3 method for finding the pivot, we already
    // know that value at the far left is smaller than the pivot and the value
    // at the far right is greater than the pivot. since we do not want to
    // disturb these values while we traverse the list but we want to move the
    // pivot out of the way , we move the pivot just to the left of the far
    // right position
    int index = left + 1;
    int pivotSwap = right - 1;
    swap(array, pivotIdx, pivotSwap);
    // loop between the left+1 bound and the right-1 bound, comparing and
    // swapping values less than the pivot value to the current index, and
    // moving the index up one on each swap
    for (int i = index; i < pivotSwap; i++) {
      if ((array[i]).compareTo(array[pivotSwap]) <= 0) {
        swap(array, i, index);
        index++;
      }
    }
    // restore the pivot to the newly found index
    swap(array, pivotSwap, index);
    return index;
  }

  /**
   * Swap two values.
   * 
   * @param array
   *          the array in which to swap two values
   * @param i
   *          the index of the first value to swap
   * @param j
   *          the index of the second value to swap
   */
  private static <T extends Comparable<T>> void swap(T[] array, int i, int j) {
    T temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
}