package Sorts;

import static Sorts.SortUtils.*;

/**
 * @author Varun Upadhyay (https://github.com/varunu28)
 * @author Podshivalov Nikita (https://github.com/nikitap492)
 * @see SortAlgorithm
 */
class QuickSort implements SortAlgorithm {

  /**
   * This method implements the Generic Quick Sort
   *
   * @param array The array to be sorted Sorts the array in increasing order
   */
  @Override
  public <T extends Comparable<T>> T[] sort(T[] array) {
    doSort(array, 0, array.length - 1);
    return array;
  }

  /**
   * The sorting process
   *
   * @param left The first index of an array
   * @param right The last index of an array
   * @param array The array to be sorted
   */
  private static <T extends Comparable<T>> void doSort(T[] array, int left, int right) {
    if (left < right) {
      int pivot = randomPartition(array, left, right);
      doSort(array, left, pivot - 1);
      doSort(array, pivot, right);
    }
  }

  /**
   * Ramdomize the array to avoid the basically ordered sequences
   *
   * @param array The array to be sorted
   * @param left The first index of an array
   * @param right The last index of an array
   * @return the partition index of the array
   */
  private static <T extends Comparable<T>> int randomPartition(T[] array, int left, int right) {
    int randomIndex = left + (int) (Math.random() * (right - left + 1));
    swap(array, randomIndex, right);
    return partition(array, left, right);
  }

  /**
   * This method finds the partition index for an array
   *
   * @param array The array to be sorted
   * @param left The first index of an array
   * @param right The last index of an array Finds the partition index of an array
   */
  private static <T extends Comparable<T>> int partition(T[] array, int left, int right) {
    int mid = (left + right) >>> 1;
    T pivot = array[mid];

    while (left <= right) {
      while (less(array[left], pivot)) {
        ++left;
      }
      while (less(pivot, array[right])) {
        --right;
      }
      if (left <= right) {
        swap(array, left, right);
        ++left;
        --right;
      }
    }
    return left;
  }

  // Driver Program
  public static void main(String[] args) {

    // For integer input
    Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};

    QuickSort quickSort = new QuickSort();
    quickSort.sort(array);

    // Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
    print(array);

    String[] stringArray = {"c", "a", "e", "b", "d"};
    quickSort.sort(stringArray);

    // Output => a	b	c	d	e
    print(stringArray);
  }
}