String-Sorting/MSD.java at main · kodi73/String-Sorting · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
packagestring;

publicclassMSD {
privatestaticString[] aux;
privatestaticfinalintR = 26;

privatestaticvoidsort(String[] a) {
aux = newString[a.length];
sort(a, aux, 0, a.length - 1, 0);
 }

privatestaticvoidsort(String[] a, String[] aux, intlo, inthi, intd) {
if (hi <= lo) return;

int[] count = newint[R + 2];

for (inti = lo; i <= hi; i++)
count[charAt(a[i], d) + 2]++;
for (intr = 0; r < R + 1; r++)
count[r + 1] += count[r];
for (inti = lo; i <= hi; i++)
aux[count[charAt(a[i], d) + 1]++] = a[i];
for (inti = lo; i <= hi; i++)
a[i] = aux[i - lo];

for (intr = 0; r < R; r++)
sort(a, aux, lo + count[r], lo + count[r + 1] - 1, d + 1);
 }

privatestaticintcharAt(Strings, intd) {
if (d < s.length()) returns.charAt(d) - 'a';
return -1;
 }

publicstaticvoidmain(String[] args) {
String[] a = {"cat", "mat", "dog", "hat", "dom", "don", "rat", "vat", "run", "cut", "pot", "lot", "put", "rub", "tub", "sub", "dub", "jug", "rug", "mug", "bug", "yak"};
intN = a.length;
for (inti = 0; i < N; i++)
System.out.print(a[i] + " ");
System.out.println();
sort(a);
for (inti = 0; i < N; i++)
System.out.print(a[i] + " ");
System.out.println();
 }
}