/**
 * Quicksort implementation of SortInterface
 * 
 * @author Alexander Schaap
 * 
 * @param <T>
 *          Type of words to be sorted
 */
public class AlphabetizerQuickSort<T extends Comparable<T>> extends
    AlphabetizerAbstract<T> {
  // attempt at singleton; running into problems with MasterControl being partly
  // static
  // private QuickSort<T> instance = new QuickSort<T>();
  // private QuickSort() { //prevent instantiation
  //
  // }
  // public SortInterface<T> getInstance() {
  // return instance;
  // }
  @Override
  public void sort(StorageInterface<StorageInterface<WordInterface<T>>> line) {
    quicksort(line, 0, line.length() - 1);
  }

  /**
   * Quicksort, as seen on Wikipedia
   * 
   * @param line
   *          - the current set of words to be sorted
   * @param i
   *          - index from which to start sorting
   * @param k
   *          - index up to (including) which to sort
   */
  private void quicksort(
      StorageInterface<StorageInterface<WordInterface<T>>> line, int i, int k) {
    if (i < k) {
      int p = partition(line, i, k);
      quicksort(line, i, p - 1);
      quicksort(line, p + 1, k);
    }
  }

  /**
   * partition function as part of quicksort
   * 
   * the only reason we need T is for compareTo
   * 
   * @param line
   *          - array to partition
   * @param left
   *          - starting index
   * @param right
   *          - ending index
   * @return - index at which second 'half' starts
   */
  private int partition(
      StorageInterface<StorageInterface<WordInterface<T>>> line, int left,
      int right) {
    // pivotIndex defaults to right; O(n^2) for already sorted arrays
    int storeIndex = left;
    for (int i = left; i < right; i++) {
      if (ordered(line, i, right)) {
        swap(line, i, storeIndex);
        storeIndex++;
      }
    }
    swap(line, right, storeIndex);

    return storeIndex;
  }
}