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}