package algs25;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Goofy.java
 *  Execution:    java Goofy N
 *
 *  Sort N random real numbers between 0 and 1 using an algorithm
 *  of Jim Huffins.
 *
 *************************************************************************/


public class XGoofy {

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

  public static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) {
    if (lo >= hi) return;
    sort(a, lo, hi-1);     // first n-1 items
    if (less(a[hi], a[hi-1])) {
      exch(a, hi-1, hi);
      sort(a, lo, hi-1);  // first n-1 items
    }
  }

  /* *********************************************************************
   *  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));
  }

}