001package algs23;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac QuickKR.java
005 *  Execution:    java QuickKR N
006 *
007 *  Generate N random real numbers between 0 and 1 and quicksort them.
008 *  Uses version of quicksort from K+R.
009 *
010 *  Reference: The C Programming Language by Brian W. Kernighan and
011 *  Dennis M. Ritchie, p. 87.
012 *
013 *************************************************************************/
014
015public class XQuickKR {
016
017        public static <T extends Comparable<? super T>> void sort(T[] a) {
018                sort(a, 0, a.length - 1);
019        }
020
021        private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) {
022                if (hi <= lo) return;
023                exch(a, lo, (lo + hi) / 2);  // use middle element as partition
024                int last = lo;
025                for (int i = lo + 1; i <= hi; i++)
026                        if (less(a[i], a[lo])) exch(a, ++last, i);
027                exch(a, lo, last);
028                sort(a, lo, last-1);
029                sort(a, last+1, hi);
030        }
031
032
033        /* *********************************************************************
034         *  Helper sorting functions
035         ***********************************************************************/
036
037        // is v < w ?
038        private static <T extends Comparable<? super T>> boolean less(T v, T w) {
039                return (v.compareTo(w) < 0);
040        }
041
042        // exchange a[i] and a[j]
043        private static void exch(Object[] a, int i, int j) {
044                Object swap = a[i];
045                a[i] = a[j];
046                a[j] = swap;
047        }
048
049
050        /* *********************************************************************
051         *  Check if array is sorted - useful for debugging
052         ***********************************************************************/
053        private static <T extends Comparable<? super T>> boolean isSorted(T[] a) {
054                for (int i = 1; i < a.length; i++)
055                        if (less(a[i], a[i-1])) return false;
056                return true;
057        }
058
059
060
061        // test client
062        public static void main(String[] args) {
063
064                // generate array of N random reals between 0 and 1
065                int N = Integer.parseInt(args[0]);
066                Double[] a = new Double[N];
067                for (int i = 0; i < N; i++) {
068                        a[i] = Math.random();
069                }
070
071                // sort the array
072                sort(a);
073
074                // display results
075                for (int i = 0; i < N; i++) {
076                        StdOut.println(a[i]);
077                }
078                StdOut.println("isSorted = " + isSorted(a));
079        }
080
081}