001/****************************************************************************** 002 * Compilation: javac Quick.java 003 * Execution: java Quick < input.txt 004 * Dependencies: System.out.java StdIn.java 005 * Data files: http://algs4.cs.princeton.edu/23quicksort/tiny.txt 006 * http://algs4.cs.princeton.edu/23quicksort/words3.txt 007 * 008 * Sorts a sequence of strings from standard input using quicksort. 009 * 010 * % more tiny.txt 011 * S O R T E X A M P L E 012 * 013 * % java Quick < tiny.txt 014 * A E E L M O P R S T X [ one string per line ] 015 * 016 * % more words3.txt 017 * bed bug dad yes zoo ... all bad yet 018 * 019 * % java Quick < words3.txt 020 * all bad bed bug dad ... yes yet zoo [ one string per line ] 021 * 022 * 023 * Remark: For a type-safe version that uses static generics, see 024 * 025 * http://algs4.cs.princeton.edu/23quicksort/QuickPedantic.java 026 * 027 ******************************************************************************/ 028package ca.bc.webarts.widgets; 029 030/** 031 * The <tt>Quick</tt> class provides static methods for sorting an 032 * array and selecting the ith smallest element in an array using quicksort. 033 * <p> 034 * For additional documentation, see <a href="http://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of 035 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. 036 * 037 * @author Robert Sedgewick 038 * @author Kevin Wayne 039 */ 040public class Quick 041{ 042 043 // This class should not be instantiated. 044 private Quick() 045 { } 046 047 048 /** 049 * Rearranges the array in ascending order, using the natural order. 050 * @param a the array to be sorted 051 */ 052 public static void sort( Comparable[] a ) 053 { 054 //StdRandom.shuffle( a ); 055 sort( a, 0, a.length - 1 ); 056 assert isSorted( a ); 057 } 058 059 060 // quicksort the subarray from a[lo] to a[hi] 061 private static void sort( Comparable[] a, int lo, int hi ) 062 { 063 if ( hi <= lo ) 064 { 065 return; 066 } 067 int j = partition( a, lo, hi ); 068 sort( a, lo, j - 1 ); 069 sort( a, j + 1, hi ); 070 assert isSorted( a, lo, hi ); 071 } 072 073 074 // partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi] 075 // and return the index j. 076 private static int partition( Comparable[] a, int lo, int hi ) 077 { 078 int i = lo; 079 int j = hi + 1; 080 Comparable v = a[lo]; 081 while ( true ) 082 { 083 084 // find item on lo to swap 085 while ( less( a[ ++i], v ) ) 086 { 087 if ( i == hi ) 088 { 089 break; 090 } 091 092 // find item on hi to swap 093 } 094 while ( less( v, a[ --j] ) ) 095 { 096 if ( j == lo ) 097 { 098 break; 099 } // redundant since a[lo] acts as sentinel 100 101 // check if pointers cross 102 } 103 if ( i >= j ) 104 { 105 break; 106 } 107 108 exch( a, i, j ); 109 } 110 111 // put partitioning item v at a[j] 112 exch( a, lo, j ); 113 114 // now, a[lo .. j-1] <= a[j] <= a[j+1 .. hi] 115 return j; 116 } 117 118 119 /** 120 * Rearranges the array so that a[k] contains the kth smallest key; 121 * a[0] through a[k-1] are less than (or equal to) a[k]; and 122 * a[k+1] through a[N-1] are greater than (or equal to) a[k]. 123 * @param a the array 124 * @param k find the kth smallest 125 */ 126 public static Comparable select( Comparable[] a, int k ) 127 { 128 if ( k < 0 || k >= a.length ) 129 { 130 throw new IndexOutOfBoundsException( "Selected element out of bounds" ); 131 } 132 //StdRandom.shuffle( a ); 133 int lo = 0, hi = a.length - 1; 134 while ( hi > lo ) 135 { 136 int i = partition( a, lo, hi ); 137 if ( i > k ) 138 { 139 hi = i - 1; 140 } 141 else if ( i < k ) 142 { 143 lo = i + 1; 144 } 145 else 146 { 147 return a[i]; 148 } 149 } 150 return a[lo]; 151 } 152 153 154 /*************************************************************************** 155 * Helper sorting functions. 156 ***************************************************************************/ 157 158 // is v < w ? 159 private static boolean less( Comparable v, Comparable w ) 160 { 161 return v.compareTo( w ) < 0; 162 } 163 164 165 // exchange a[i] and a[j] 166 private static void exch( Object[] a, int i, int j ) 167 { 168 Object swap = a[i]; 169 a[i] = a[j]; 170 a[j] = swap; 171 } 172 173 174 /*************************************************************************** 175 * Check if array is sorted - useful for debugging. 176 ***************************************************************************/ 177 private static boolean isSorted( Comparable[] a ) 178 { 179 return isSorted( a, 0, a.length - 1 ); 180 } 181 182 183 private static boolean isSorted( Comparable[] a, int lo, int hi ) 184 { 185 for ( int i = lo + 1; i <= hi; i++ ) 186 { 187 if ( less( a[i], a[i - 1] ) ) 188 { 189 return false; 190 } 191 } 192 return true; 193 } 194 195 196 // print array to standard output 197 private static void show( Comparable[] a ) 198 { 199 for ( int i = 0; i < a.length; i++ ) 200 { 201 System.out.println( a[i] ); 202 } 203 } 204 205 206 /** 207 * Reads in a sequence of strings from standard input; quicksorts them; 208 * and prints them to standard output in ascending order. 209 * Shuffles the array and then prints the strings again to 210 * standard output, but this time, using the select method. 211 */ 212 public static void main( String[] args ) 213 { 214 String[] a = args;// StdIn.readAllStrings(); 215 Quick.sort( a ); 216 show( a ); 217 218 // shuffle 219 // StdRandom.shuffle( a ); 220 221 // display results again using select 222 System.out.println(); 223 for ( int i = 0; i < a.length; i++ ) 224 { 225 String ith = ( String ) Quick.select( a, i ); 226 System.out.println( ith ); 227 } 228 } 229 230} 231