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}