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

W₄ : hefe bach gaga cafe geha

W₃ : gaga geha hefe cafe bach

W₂ : bach hefe cafe gaga geha

W₁ : bach cafe gaga hefe geha

W₀ : bach cafe gaga geha hefe

Die zugehörigen Buckets lauten:

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.