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}