001package algs23; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac Quick.java 005 * Execution: java Quick < input.txt 006 * Dependencies: StdOut.java StdIn.java 007 * Data files: http://algs4.cs.princeton.edu/23quicksort/tiny.txt 008 * http://algs4.cs.princeton.edu/23quicksort/words3.txt 009 * 010 * Sorts a sequence of strings from standard input using quicksort. 011 * 012 * % more tiny.txt 013 * S O R T E X A M P L E 014 * 015 * % java Quick < tiny.txt 016 * A E E L M O P R S T X [ one string per line ] 017 * 018 * % more words3.txt 019 * bed bug dad yes zoo ... all bad yet 020 * 021 * % java Quick < words3.txt 022 * all bad bed bug dad ... yes yet zoo [ one string per line ] 023 * 024 *************************************************************************/ 025 026public class Quick { 027 028 // quicksort the array 029 public static <T extends Comparable<? super T>> void sort(T[] a) { 030 StdRandom.shuffle(a); 031 sort(a, 0, a.length - 1); 032 } 033 034 // quicksort the subarray from a[lo] to a[hi] 035 private static <T extends Comparable<? super T>> void sort(T[] a, int lo, int hi) { 036 if (hi <= lo) return; 037 int j = partition(a, lo, hi); 038 sort(a, lo, j-1); 039 sort(a, j+1, hi); 040 assert isSorted(a, lo, hi); 041 } 042 043 // partition the subarray a[lo .. hi] by returning an index j 044 // so that a[lo .. j-1] <= a[j] <= a[j+1 .. hi] 045 private static <T extends Comparable<? super T>> int partition(T[] a, int lo, int hi) { 046 int i = lo; 047 int j = hi + 1; 048 T v = a[lo]; 049 while (true) { 050 051 // find item on lo to swap 052 while (less(a[++i], v)) 053 if (i == hi) break; 054 055 // find item on hi to swap 056 while (less(v, a[--j])) 057 if (j == lo) break; // redundant since a[lo] acts as sentinel 058 059 // check if pointers cross 060 if (i >= j) break; 061 062 exch(a, i, j); 063 } 064 065 // put v = a[j] into position 066 exch(a, lo, j); 067 068 // with a[lo .. j-1] <= a[j] <= a[j+1 .. hi] 069 return j; 070 } 071 072 /* ********************************************************************* 073 * Rearranges the elements in a so that a[k] is the kth smallest element, 074 * and a[0] through a[k-1] are less than or equal to a[k], and 075 * a[k+1] through a[n-1] are greater than or equal to a[k]. 076 ***********************************************************************/ 077 public static <T extends Comparable<? super T>> T select(T[] a, int k) { 078 if (k < 0 || k >= a.length) { 079 throw new Error("Selected element out of bounds"); 080 } 081 StdRandom.shuffle(a); 082 int lo = 0, hi = a.length - 1; 083 while (hi > lo) { 084 int i = partition(a, lo, hi); 085 if (i > k) hi = i - 1; 086 else if (i < k) lo = i + 1; 087 else return a[i]; 088 } 089 return a[lo]; 090 } 091 092 093 094 /* ********************************************************************* 095 * Helper sorting functions 096 ***********************************************************************/ 097 098 // is v < w ? 099 private static <T extends Comparable<? super T>> boolean less(T v, T w) { 100 if (COUNT_OPS) DoublingTest.incOps (); 101 return (v.compareTo(w) < 0); 102 } 103 104 // exchange a[i] and a[j] 105 private static <T> void exch(T[] a, int i, int j) { 106 if (COUNT_OPS) DoublingTest.incOps (); 107 T swap = a[i]; 108 a[i] = a[j]; 109 a[j] = swap; 110 } 111 112 113 /* ********************************************************************* 114 * Check if array is sorted - useful for debugging 115 ***********************************************************************/ 116 private static <T extends Comparable<? super T>> boolean isSorted(T[] a) { 117 return isSorted(a, 0, a.length - 1); 118 } 119 120 private static <T extends Comparable<? super T>> boolean isSorted(T[] a, int lo, int hi) { 121 for (int i = lo + 1; i <= hi; i++) 122 if (less(a[i], a[i-1])) return false; 123 return true; 124 } 125 126 127 // print array to standard output 128 private static <T> void show(T[] a) { 129 for (T element : a) { 130 StdOut.println(element); 131 } 132 } 133 134 // test code 135 private static boolean COUNT_OPS = false; 136 public static void main(String[] args) { 137 //String[] cards = In.readStrings ("data/cards.txt"); 138 //StdRandom.shuffle (cards); 139 140 //StdIn.fromFile ("data/tiny.txt"); 141 //StdIn.fromFile ("data/cards.txt"); 142 StdIn.fromFile ("data/words3.txt"); 143 144 String[] a = StdIn.readAllStrings(); 145 sort(a); 146 show(a); 147 148 // display results again using select 149 StdOut.println(); 150 for (int i = 0; i < a.length; i++) { 151 String ith = select(a, i); 152 StdOut.println(ith); 153 } 154 155 COUNT_OPS = true; 156 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandomUnique (N), (Integer[] x) -> sort (x)); 157 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerRandom (N, 2), (Integer[] x) -> sort (x)); 158 DoublingTest.run (20000, 5, N -> ArrayGenerator.integerPartiallySortedUnique (N), (Integer[] x) -> sort (x)); 159 } 160 161}