001package algs51; // section 5.1
002import stdlib.*;
003/* *********************************************************************************
004 *  Compilation: javac Quick3string.java
005 *  Execution:   java Quick3string < input.txt
006 *
007 *  Reads string from standard input and 3-way string quicksort them.
008 *
009 *  WARNING: This program assumes that the {@code substring()} method takes
010 *  constant time and space. Beginning with Oracle / OpenJDK Java 7, Update 6,
011 *  the substring method takes linear time and space in the size of the
012 *  extracted substring. Do NOT use this code with such versions.
013 *
014 *  To fix: replace less() with a version that uses charAt().
015 *
016 *  PATCH HAS BEEN APPLIED HERE: See less() versus less1() below.
017 *
018 *  % java Quick3string < shell.txt
019 *  are
020 *  by
021 *  sea
022 *  seashells
023 *  seashells
024 *  sells
025 *  sells
026 *  she
027 *  she
028 *  shells
029 *  shore
030 *  surely
031 *  the
032 *  the
033 *
034 * MAX_LENGTH = 64
035 * RESULTS WITH Arrays.sort (Mergesort)
036 *
037 *     $ ./runjava algs51.Quick3string
038 *       256000 [0.282 0.876]
039 *       512000 [0.384 1.362]
040 *      1024000 [0.839 2.185]
041 *     $ ./runjava algs51.Quick3string
042 *       256000 [0.291 1.003]
043 *       512000 [0.380 1.306]
044 *      1024000 [0.880 2.316]
045 *     $ ./runjava algs51.Quick3string
046 *       256000 [0.243 0.721]
047 *       512000 [0.396 1.630]
048 *      1024000 [0.846 2.136]
049 *
050 * RESULTS with Quick3string (with less implemented using charAt)
051 *
052 *     $ ./runjava  algs51.Quick3string
053 *       256000 [0.108 1.714]
054 *       512000 [0.248 2.296]
055 *      1024000 [0.567 2.286]
056 *     $ ./runjava  algs51.Quick3string
057 *       256000 [0.104 1.576]
058 *       512000 [0.250 2.404]
059 *      1024000 [0.605 2.420]
060 *     $ ./runjava  algs51.Quick3string
061 *       256000 [0.110 1.746]
062 *       512000 [0.261 2.373]
063 *      1024000 [0.589 2.257]
064 *
065 * RESULTS with Quick3string (with less implemented using substring)
066 *
067 *     $ ./runjava  algs51.Quick3string
068 *       256000 [0.251 0.815]
069 *       512000 [0.422 1.681]
070 *      1024000 [0.893 2.116]
071 *     $ ./runjava  algs51.Quick3string
072 *       256000 [0.235 0.739]
073 *       512000 [0.404 1.719]
074 *      1024000 [0.883 2.186]
075 *     $ ./runjava  algs51.Quick3string
076 *       256000 [0.265 0.828]
077 *       512000 [0.413 1.558]
078 *      1024000 [0.886 2.145]
079 *
080 * RESULTS WITH Arrays.sort (Mergesort)
081 *
082 *     $ ./runjava algs51.Quick3string
083 *     dickens: [6.855]
084 *     $ ./runjava algs51.Quick3string
085 *     dickens: [3.650]
086 *     $ ./runjava algs51.Quick3string
087 *     dickens: [4.384]
088 *
089 * RESULTS with Quick3string (with less implemented using charAt)
090 *
091 *     $ ./runjava algs51.Quick3string
092 *     dickens: [2.103]
093 *     $ ./runjava algs51.Quick3string
094 *     dickens: [2.309]
095 *     $ ./runjava algs51.Quick3string
096 *     dickens: [2.136]
097 *
098 * RESULTS with Quick3string (with less implemented using substring)
099 *
100 *     $ ./runjava algs51.Quick3string
101 *     dickens: [6.783]
102 *     $ ./runjava algs51.Quick3string
103 *     dickens: [7.296]
104 *     $ ./runjava algs51.Quick3string
105 *     dickens: [6.995]
106 *
107 ***********************************************************************************/
108
109public class Quick3string {
110        private static final int CUTOFF =  15;   // cutoff to insertion sort
111
112        // sort the array a[] of strings
113        public static void sort(String[] a) {
114                // StdRandom.shuffle(a);
115                sort(a, 0, a.length-1, 0);
116                assert isSorted(a);
117        }
118
119        // return the dth character of s, -1 if d = length of s
120        private static int charAt(String s, int d) {
121                assert d >= 0 && d <= s.length();
122                if (d == s.length()) return -1;
123                return s.charAt(d);
124        }
125
126
127        // 3-way string quicksort a[lo..hi] starting at dth character
128        private static void sort(String[] a, int lo, int hi, int d) {
129
130                // cutoff to insertion sort for small subarrays
131                if (hi <= lo + CUTOFF) {
132                        insertion(a, lo, hi, d);
133                        return;
134                }
135
136                int lt = lo, gt = hi;
137                int v = charAt(a[lo], d);
138                int i = lo + 1;
139                while (i <= gt) {
140                        int t = charAt(a[i], d);
141                        if      (t < v) exch(a, lt++, i++);
142                        else if (t > v) exch(a, i, gt--);
143                        else              i++;
144                }
145
146                // a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
147                sort(a, lo, lt-1, d);
148                if (v >= 0) sort(a, lt, gt, d+1);
149                sort(a, gt+1, hi, d);
150        }
151
152        // sort from a[lo] to a[hi], starting at the dth character
153        private static void insertion(String[] a, int lo, int hi, int d) {
154                for (int i = lo; i <= hi; i++)
155                        for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
156                                exch(a, j, j-1);
157        }
158
159        // exchange a[i] and a[j]
160        private static void exch(String[] a, int i, int j) {
161                String temp = a[i];
162                a[i] = a[j];
163                a[j] = temp;
164        }
165
166        // is v less than w, starting at character d
167        private static boolean less1(String v, String w, int d) {
168                assert v.substring(0, d).equals(w.substring(0, d));
169                return v.substring(d).compareTo(w.substring(d)) < 0;
170        }
171
172        // is v less than w, starting at character d
173        private static boolean less(String v, String w, int d) {
174                assert v.substring(0, d).equals(w.substring(0, d));
175                int len1 = v.length ();
176                int len2 = w.length ();
177                int n = Math.min(len1, len2);
178                int k = 0;
179                while (k < n) {
180                        char c1 = v.charAt (k);
181                        char c2 = w.charAt (k);
182                        if (c1 != c2)
183                                return c1 < c2;
184                        k++;
185                }
186                return len1 < len2;
187        }
188
189
190        // is the array sorted
191        private static boolean isSorted(String[] a) {
192                for (int i = 1; i < a.length; i++)
193                        if (a[i].compareTo(a[i-1]) < 0) return false;
194                return true;
195        }
196
197
198        /* *********************************************************************************
199         *  Test code
200         ***********************************************************************************/
201        private static final int MAX_LENGTH = 64;
202        private static final String CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()_-+={[}]\\|:;'\"<>,./?";
203        private static String randomString() {
204                int length = 2 + StdRandom.uniform (MAX_LENGTH);
205                char[] text = new char[length];
206                int NUM_CHARACTERS = CHARACTERS.length ();
207                for (int i = 0; i < length; i++) {
208                        text[i] = CHARACTERS.charAt(StdRandom.uniform (NUM_CHARACTERS));
209                }
210                return new String(text);
211        }
212        private static void exch(int[] a, int i, int j) {
213                int swap = a[i];
214                a[i] = a[j];
215                a[j] = swap;
216        }
217        private static double time;
218        private static void countops (int N) {
219                String[] a = new String[N];
220                for (int i = 0; i < a.length; i++) a[i] = randomString ();
221                //Arrays.sort (a);
222                //Arrays.sort (a); for (int i = 0; i < (N-1)/2; i++) exch(a, i, N-i-1);
223
224                Stopwatch sw = new Stopwatch ();
225                sort (a);
226                //Arrays.sort (a);
227                time = sw.elapsedTime ();
228        }
229        public static void main(String[] args) {
230                int N = 128000;
231                countops (N);
232                //System.exit (0);
233                double prevTime = time;
234                for (int i=0; i<3; i++) {
235                        N *= 2;
236                        countops (N);
237                        StdOut.format("%8d [%5.3f %5.3f]\n", N, time, time/prevTime);
238                        prevTime = time;
239                }
240        }
241        public static void main1(String[] args) {
242                String[] a = new In("data/dickens.txt").readAllStrings ();
243                Stopwatch sw = new Stopwatch ();
244                sort (a);
245                //Arrays.sort (a);
246                StdOut.format("dickens: [%5.3f]\n", sw.elapsedTime ());
247        }
248        public static void main2(String[] args) {
249                // read in the strings from standard input
250                String[] a = StdIn.readAllStrings();
251                int N = a.length;
252
253                // sort the strings
254                sort(a);
255
256                // print the results
257                for (int i = 0; i < N; i++)
258                        StdOut.println(a[i]);
259        }
260}