001package algs25;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac Goofy.java
005 *  Execution:    java Goofy N
006 *
007 *  Sort N random real numbers between 0 and 1 using an algorithm
008 *  of Jim Huffins.
009 *
010 *************************************************************************/
011
012
013public class XGoofy {
014
015        public static <T extends Comparable<? super T>> void sort(T[] a) {
016                sort(a, 0, a.length-1);
017        }
018
019        public static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) {
020                if (lo >= hi) return;
021                sort(a, lo, hi-1);     // first n-1 items
022                if (less(a[hi], a[hi-1])) {
023                        exch(a, hi-1, hi);
024                        sort(a, lo, hi-1);  // first n-1 items
025                }
026        }
027
028        /* *********************************************************************
029         *  Helper sorting functions
030         ***********************************************************************/
031
032        // is v < w ?
033        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
034                return v.compareTo(w) < 0;
035        }
036
037        // exchange a[i] and a[j]
038        private static void exch(Object[] a, int i, int j) {
039                Object swap = a[i];
040                a[i] = a[j];
041                a[j] = swap;
042        }
043
044
045        /* *********************************************************************
046         *  Check if array is sorted - useful for debugging
047         ***********************************************************************/
048        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
049                for (int i = 1; i < a.length; i++)
050                        if (less(a[i], a[i-1])) return false;
051                return true;
052        }
053
054
055
056        // test client
057        public static void main(String[] args) {
058
059                // generate array of N random reals between 0 and 1
060                int N = Integer.parseInt(args[0]);
061                Double[] a = new Double[N];
062                for (int i = 0; i < N; i++) {
063                        a[i] = Math.random();
064                }
065
066                // sort the array
067                sort(a);
068
069                // display results
070                for (int i = 0; i < N; i++) {
071                        StdOut.println(a[i]);
072                }
073                StdOut.println("isSorted = " + isSorted(a));
074        }
075
076}