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}, \ldots, W_{0}$ gebildet.
$W_N$ enthält die unsortierten Wörter in der gegebenen initialen Reihenfolge.
$W_j$ mit $j \in [0, \ldots, N-1]$ enthält alle Wörter, aufsteigend sortiert bezüglich der Positionen $j + 1, \ldots, N$ .
Das Ergebnis der Sortiervorgänge ist $W_0$.

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):

$W_4$:	hefe bach gaga cafe geha
$W_3$:	gaga geha hefe cafe bach
$W_2$:	bach hefe cafe gaga geha
$W_1$:	bach cafe gaga hefe geha
$W_0$:	bach cafe gaga geha hefe

Die zugehörigen Buckets lauten:

	$W_4 \rightarrow W_3$	$W_3 \rightarrow W_2$	$W_2 \rightarrow W_1$	$W_1 \rightarrow W_0$
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\vert$ 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\vert$

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_3$ verteilt wird.

Der Aufwand zum Verteilen und Aufsammeln der Listen $W_{N}, \ldots, W_{0}$ 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.