Hier einmal mit ArrayDeque:
int len = 0;
for (String string : strings) {
if (string.length() > len) {
len = string.length();
}
}
ArrayDeque<String>[] box = new ArrayDeque[256];
for (int i = 0; i < box.length; i++) {
box** = new ArrayDeque<String>();
}
for (int i = len - 1; i >= 0; i--) {
//partitionieren
for (String string : strings) {
if (i >= string.length()) {
box[0].add(string);
} else {
box[string.charAt(i)].add(string);
}
}
//aufsammeln
int j = 0;
for (ArrayDeque<String> arrayDeque : box) {
while (!arrayDeque.isEmpty()) {
strings[j++] = arrayDeque.remove();
}
}
}
}```
Und ein Microbenchmark dazu:
``` public static void main(String[] args) {
String[] s = "aaaa aaa Es war ein mal ein Latten zaun, mit Zwischen raum, um hin durch zu schauen".split(" ");
sortiereStringsNachRadixsort(s);
System.out.println(Arrays.toString(s));
//microbenchmark
Random r = new Random();
s = new String[100000];
System.arraycopy("eins zwei drei".split(" "), 0, s, 0, 3);
for (int i = 3; i < s.length; i++) {
s** = s[r.nextInt(3)];
}
String[] s1 = new String[s.length];
System.arraycopy(s, 0, s1, 0, s.length);
long t1 = System.currentTimeMillis();
Arrays.sort(s1);
long t2 = System.currentTimeMillis();
System.out.println(s1[0] + " " + s1[1] + " " + s1[2]);
s1 = new String[s.length];
System.arraycopy(s, 0, s1, 0, s.length);
long t3 = System.currentTimeMillis();
sortiereStringsNachRadixsort(s1);
long t4 = System.currentTimeMillis();
System.out.println(s1[0] + " " + s1[1] + " " + s1[2]);
System.out.println(s[0] + " " + s[1] + " " + s[2]);
System.out.println("modified qs: " + (t2 - t1));
System.out.println("rs (deque-impl): " + (t4 - t3));
}```
Jetzt passiert etwas Erstaunliches, obwohl ich das nicht mit Arrays primitiver Typen realisiert habe, ist das (lineare) Sortierverfahren in diesem Falle etwas schneller als QuickSort:
run:
[Es, Latten, Zwischen, aaa, aaaa, durch, ein, ein, hin, mal, mit, raum, schauen, um, war, zaun, zu]
drei drei drei
drei drei drei
eins zwei drei
modified qs: 395
rs (deque-impl): 42
BUILD SUCCESSFUL (total time: 0 seconds)
Grüßle
*** Edit ***
Mhm, schon wieder geirrt, Arrays.sort(s1) kein QS, sondern whrs. MergeSort.
Wenn man das Sortierverfahren einmal aufschreibt, hat man es schnell gelernt. :verzweifel:
Ich kann mich daran erinnern das mein Tutor mir einmal Radixsort erklären wollte, ich in der Stunde aber geschlafen habe. Und dann wollte unser Prof. einmal einen Beweis vorbringen, als ich zuvor allerdings ziehmlich auffällig den Raum verlassen habe. Kein Wunder, das ich von der Uni geflogen bin.
Aber ich habe auch gelesen, das besserbegabte Kinder schlechter lernen können als andere, weil sie "das richtige$ Lernen niemals gelernt haben, resp. anders lernen als andere.
Aber die Schulzeit ist ja auch schon etwas länger her, und das andere heißt sich ja auch "Erwachsenenbildung". :verzweifel: