package algs23;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac QuickKR.java
 *  Execution:    java QuickKR N
 *
 *  Generate N random real numbers between 0 and 1 and quicksort them.
 *  Uses version of quicksort from K+R.
 *
 *  Reference: The C Programming Language by Brian W. Kernighan and
 *  Dennis M. Ritchie, p. 87.
 *
 *************************************************************************/

public class XQuickKR {

  public static <T extends Comparable<? super T>> void sort(T[] a) {
    sort(a, 0, a.length - 1);
  }

  private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) {
    if (hi <= lo) return;
    exch(a, lo, (lo + hi) / 2);  // use middle element as partition
    int last = lo;
    for (int i = lo + 1; i <= hi; i++)
      if (less(a[i], a[lo])) exch(a, ++last, i);
    exch(a, lo, last);
    sort(a, lo, last-1);
    sort(a, last+1, hi);
  }


  /* *********************************************************************
   *  Helper sorting functions
   ***********************************************************************/

  // is v < w ?
  private static <T extends Comparable<? super T>> boolean less(T v, T w) {
    return (v.compareTo(w) < 0);
  }

  // exchange a[i] and a[j]
  private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
  }


  /* *********************************************************************
   *  Check if array is sorted - useful for debugging
   ***********************************************************************/
  private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
    for (int i = 1; i < a.length; i++)
      if (less(a[i], a[i-1])) return false;
    return true;
  }



  // test client
  public static void main(String[] args) {

    // generate array of N random reals between 0 and 1
    int N = Integer.parseInt(args[0]);
    Double[] a = new Double[N];
    for (int i = 0; i < N; i++) {
      a[i] = Math.random();
    }

    // sort the array
    sort(a);

    // display results
    for (int i = 0; i < N; i++) {
      StdOut.println(a[i]);
    }
    StdOut.println("isSorted = " + isSorted(a));
  }

}