Radix Sort

Idee:

Sortieren von Strings über einem endlichen Alphabet durch mehrmaliges Anwenden von Bucket Sort.

Es soll eine Liste von Wörtern mit insgesamt n Buchstaben in O(n) sortiert werden. Pro Buchstabe des Alphabets existiert ein Bucket.

Zunächst wird angenommen, dass alle Wörter die Länge N haben.

Es werden sukzessive Listen W_N, W_{N - 1},..., W₀ gebildet.
W_N enthält die unsortierten Wörter in der gegebenen initialen Reihenfolge.
W_j mit j [0,..., N - 1] enthält alle Wörter, aufsteigend sortiert bezüglich der Positionen j + 1,..., N .
Das Ergebnis der Sortiervorgänge ist W₀.

for (j = N; j > 0; j--) {
     verteile die Wörter aus W_j
     gemäß j-tem Buchstaben
     auf die Buckets;
     sammele Buckets auf nach W_{j - 1}
}

Beispiel:

Zu sortieren seien die Strings

hefe  bach  gaga  cafe  geha

Es entstehen nacheinander folgende Listen (unterstrichen ist jeweils der Buchstabe, der im nächsten Schritt zum Verteilen benutzt wird):

W4:	hefe bach gaga cafe geha
W3:	gaga geha hefe cafe bach
W2:	bach hefe cafe gaga geha
W1:	bach cafe gaga hefe geha
W0:	bach cafe gaga geha hefe

Die zugehörigen Buckets lauten:

	W4 W3	W3 W2	W2 W1	W1 W0
a	gaga geha		bach cafe gaga
b				bach
c		bach		cafe
d
e	hefe cafe		hefe geha
f		hefe cafe
g		gaga		gaga geha
h	bach	geha		hefe

Beim Aufsammeln werden die Buckets in alphabetischer Reihenfolge durchlaufen und ihre Inhalte konkateniert.

Um beim Einsammeln der Buckets nur die gefüllten anzufassen, ist es hilfreich, zu Beginn

    char[][] nichtleer;

anzulegen. nichtleer[j] enthält die Buchstaben, welche in den zu sortierenden Wörtern an j-ter Position vorkommen. Verteile hierzu zunächst Positionen auf Buchstaben:

pos[x]={j| Buchstabe x kommt an j-ter Position vor }

x	pos[x]
a	2 2 4 2 4
b	1
c	3 1
d
e	2 4 4 2
f	3 3
g	1 3 1
h	1 4 3

Nach dem Einsammeln der Buckets werden die Buchstaben auf Positionen verteilt:

j	nichtleer[j]
1	b c g g h
2	a a a e e
3	c f f g h
4	a a e e h

Obacht:

Bei der Konstruktion von nichtleer müssen doppelte Einträge vermieden werden (möglich, da sie hintereinander stehen würden).

Bei Vermeidung der Doppelten hat nichtleer[j] folgende Gestalt:

j	nichtleer[j]
1	b c g h
2	a e
3	c f g h
4	a e h

Der Aufwand zur Konstruktion von nichtleer beträgt O(n). Jedes Wort wird bzgl. jedes Buchstabens einmal verteilt und einmal aufgesammelt, jeweils in konstanter Zeit.

Bei Wörtern unterschiedlicher Länge bilde zunächst

laenge[j] = {w|

Länge von Wort w = j}

Der Aufwand hierfür beträgt O(n).

Verteile im j-ten Durchlauf zunächst alle Wörter aus laenge[j];
z.B. fad wird bzgl. des 3. Buchstabens verteilt, bevor W₃ verteilt wird.

Der Aufwand zum Verteilen und Aufsammeln der Listen W_N,..., W₀ beträgt O(n), da jedes Zeichen einmal zum Verteilen benutzt wird und einmal beim Aufsammeln unter Vermeidung der nichtleeren Buckets zu einem Schritt beiträgt.