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}