001package algs51; // section 5.1
002import stdlib.*;
003/* *********************************************************************************
004 *  Compilation: javac LSD.java
005 *  Execution:   java LSD < input.txt
006 *
007 *  LSD radix sort an array of extended ASCII strings, each of length W.
008 *
009 *  % java LSD < words3.txt
010 *  all
011 *  bad
012 *  bed
013 *  bug
014 *  dad
015 *  ...
016 *  yes
017 *  yet
018 *  zoo
019 *
020 * LENGTH = 8
021 * RESULTS WITH Arrays.sort (Mergesort)
022 *
023 *     $ ./runjava algs51.LSD
024 *       256000 [0.239 0.879]
025 *       512000 [0.303 1.268]
026 *      1024000 [0.750 2.475]
027 *     $ ./runjava algs51.LSD
028 *       256000 [0.224 0.783]
029 *       512000 [0.302 1.348]
030 *      1024000 [0.763 2.526]
031 *     $ ./runjava algs51.LSD
032 *       256000 [0.261 0.839]
033 *       512000 [0.306 1.172]
034 *      1024000 [0.738 2.412]
035 *
036 * RESULTS with LSD
037 *
038 *     $ ./runjava algs51.LSD
039 *       256000 [0.463 1.564]
040 *       512000 [0.990 2.138]
041 *      1024000 [2.293 2.316]
042 *     $ ./runjava algs51.LSD
043 *       256000 [0.442 1.811]
044 *       512000 [0.956 2.163]
045 *      1024000 [2.251 2.355]
046 *     $ ./runjava algs51.LSD
047 *       256000 [0.440 1.753]
048 *       512000 [0.958 2.177]
049 *      1024000 [2.278 2.378]
050 *
051 * LENGTH = 4
052 * RESULTS WITH Arrays.sort (Mergesort)
053 *
054 *     $ #ARRAYS 4
055 *     $ ./runjava algs51.LSD
056 *       256000 [0.259 0.893]
057 *       512000 [0.345 1.332]
058 *      1024000 [0.762 2.209]
059 *     $ ./runjava algs51.LSD
060 *       256000 [0.267 0.837]
061 *       512000 [0.953 3.569]
062 *      1024000 [1.625 1.705]
063 *     $ ./runjava algs51.LSD
064 *       256000 [0.252 1.016]
065 *       512000 [0.964 3.825]
066 *      1024000 [1.629 1.690]
067 *
068 * RESULTS with LSD
069 *
070 *     $ ./runjava algs51.LSD
071 *       256000 [0.185 1.350]
072 *       512000 [0.844 4.562]
073 *      1024000 [1.862 2.206]
074 *     $ ./runjava algs51.LSD
075 *       256000 [0.179 1.366]
076 *       512000 [0.813 4.542]
077 *      1024000 [1.827 2.247]
078 *     $ ./runjava algs51.LSD
079 *       256000 [0.178 1.348]
080 *       512000 [0.815 4.579]
081 *      1024000 [1.848 2.267]
082 *
083 ***********************************************************************************/
084
085public class LSD {
086
087        // LSD radix sort
088        public static void sort(String[] a, int W) {
089                int N = a.length;
090                int R = 256;   // extend ASCII alphabet size
091                String[] aux = new String[N];
092
093                for (int d = W-1; d >= 0; d--) {
094                        // sort by key-indexed counting on dth character
095
096                        // compute frequency counts
097                        int[] count = new int[R+1];
098                        for (int i = 0; i < N; i++)
099                                count[a[i].charAt(d) + 1]++;
100
101                        // compute cumulates
102                        for (int r = 0; r < R; r++)
103                                count[r+1] += count[r];
104
105                        // move data
106                        for (int i = 0; i < N; i++)
107                                aux[count[a[i].charAt(d)]++] = a[i];
108
109                        // copy back
110                        for (int i = 0; i < N; i++)
111                                a[i] = aux[i];
112                }
113        }
114
115
116        /* *********************************************************************************
117         *  Test code
118         ***********************************************************************************/
119        private static final int LENGTH = 4;
120        private static final String CHARACTERS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789`~!@#$%^&*()_-+={[}]\\|:;'\"<>,./?";
121        private static String randomString() {
122                char[] text = new char[LENGTH];
123                int NUM_CHARACTERS = CHARACTERS.length ();
124                for (int i = 0; i < LENGTH; i++) {
125                        text[i] = CHARACTERS.charAt(StdRandom.uniform (NUM_CHARACTERS));
126                }
127                return new String(text);
128        }
129        private static void exch(int[] a, int i, int j) {
130                int swap = a[i];
131                a[i] = a[j];
132                a[j] = swap;
133        }
134        private static double time;
135        private static void countops (int N) {
136                String[] a = new String[N];
137                //for (int i = 0; i < a.length; i++) a[i] = (N*i)/N;
138                //StdRandom.shuffle (a);
139                for (int i = 0; i < a.length; i++) a[i] = randomString ();
140                //Arrays.sort (a);
141                //Arrays.sort (a); for (int i = 0; i < (N-1)/2; i++) exch(a, i, N-i-1);
142
143                Stopwatch sw = new Stopwatch ();
144                sort (a, LENGTH);
145                //Merge.sort (a);
146                //Arrays.sort (a);
147                time = sw.elapsedTime ();
148        }
149        public static void main(String[] args) {
150                int N = 128000;
151                countops (N);
152                //System.exit (0);
153                double prevTime = time;
154                for (int i=0; i<3; i++) {
155                        N *= 2;
156                        countops (N);
157                        StdOut.format("%8d [%5.3f %5.3f]\n", N, time, time/prevTime);
158                        prevTime = time;
159                }
160        }
161        public static void main2(String[] args) {
162                StdIn.fromFile ("data/words3.txt");
163                String[] a = StdIn.readAllStrings();
164                int N = a.length;
165
166                // check that strings have fixed length
167                int W = a[0].length();
168                for (int i = 0; i < N; i++)
169                        assert a[i].length() == W : "Strings must have fixed length";
170
171                // sort the strings
172                sort(a, W);
173
174                // print results
175                for (int i = 0; i < N; i++)
176                        StdOut.println(a[i]);
177        }
178}