Kurs:Algorithmen und Datenstrukturen/Kapitel 2/RadixSort

RadixSort wurde 1887 von Herman Hollerith entwickelt und diente dem Sortieren von nummerierten Lochkarten.

Als Vorläufer von RadixSort kann BucketSort in seiner natürlichen Ausprägung gelten. Sollen etwa dreistellig nummerierte Datensätze sortiert werden, verteilt man die Datensätze zunächst entsprechend der Hunderterstelle auf zehn Eimer. Dann nimmt man jeden dieser Eimer und verteilt die Datensätze entsprechend der Zehnerstelle wiederum auf zehn Eimer. Jetzt stehen schon 110 Eimer auf dem Tisch. Bearbeitet man auch noch die Einerstellen simultan, hat man 1.110 Eimer zu verwalten. Man muß also sehr auf Ordnung achten.

Holleriths geniale Idee war nun, diese Arbeitsreihenfolge einfach umzukehren, wodurch sich das Ordnungsproblem von Bucketsort umgehen läßt. Die Aufgabe, die die vielen Eimer hatten, wird jetzt durch die Schichten im Stapel übernommen. Nach dem ersten Einsammeln befinden sich unten im Gesamtstapel alle Datensätze deren Schlüssel auf Null endet. Da diese Datensätze die ersten sind, die beim Auswerten der Zehnerstelle wieder auf die Schächte verteilt werden, ergeben sich dort wieder Schichtungen. Im Schacht für die Zehnerstelle Null liegen zuunterst die Datensätze, deren Einerstelle 0 ist. Darauf liegen die Datensätze mit Endziffer 1, dem folgen die mit Endziffer 2 und so weiter. Wenn die Datensätze wieder eingesammelt werden, hat der Gesamtstapel bis zu 100 Schichten (es können weniger sein, weil irgendwelche Endkombinationen nicht vorkommen). Beim Sortieren nach der Hunderterstelle wiederholt sich die Reihenfolge dieser Schichtungen in jedem Ablagefach. Man hat also virtuell 1.000 Eimer, obwohl man immer nur 10 benutzt.

Um eine bessere Übersicht über das Verfahren zu ermöglichen, werden wir zunächst dreistellige Zahlen sortieren.

Dies sei der Lochkartenstapel mit den jeweiligen Nummern.

387 310 529 174 011 227 020 901 522 771 993 348 974 213 226 004 918 098 107 109

Es wird zuerst nach der letzten Ziffer sortiert; da es zehn verschiedene Ziffern gibt benötigt man zehn Eimer. Die Datensätze werden nach der Einerstelle wie folgt auf die Eimer verteilt:

E-0 E-1 E-2 E-3 E-4 E-5 E-6 E-7 E-8 E-9 -------------------------------------------------------------------------- 310 011 522 993 174 226 387 348 529 020 901 213 974 227 918 109 771 004 107 098

Jetzt werden der Reihe nach die Eimerinhalte eingesammelt, ohne die Reihenfolg innerhalb der Eimer zu verändern.

310 020 011 901 771 522 993 213 174 974 004 226 387 227 107 348 918 098 529 109

Nun erfolgt die Sortierung nach den Zehnerstellen.

E-0 E-1 E-2 E-3 E-4 E-5 E-6 E-7 E-8 E-9 -------------------------------------------------------------------------- 901 310 020 348 771 387 993 004 011 522 174 098 107 213 226 974 109 918 227 529

Schaut man sich jetzt die Eimerinhalte an, so sieht man, dass die Einerstelle innerhalb eines Eimers immer noch aufsteigend sortiert ist. Um auch noch nach der Hunderterstelle sortieren zu können, werden die Datensätze wieder eingesammelt, ohne die Sortierung innerhalb der Eimer zu verändern.

901 004 107 109 310 011 213 918 020 522 226 227 529 348 771 174 974 387 993 098

Zum Abschluss wird nach den Hunderterstellen sortiert.

E-0 E-1 E-2 E-3 E-4 E-5 E-6 E-7 E-8 E-9 -------------------------------------------------------------------------- 004 107 213 310 522 771 901 011 109 226 348 529 918 020 174 227 387 974 098 993

Werden jetzt abschliessend die Datensätze eingesammelt ist die Sortierung abgeschlossen.

004 011 020 098 107 109 174 213 226 227 310 348 387 522 529 771 901 918 974 993

Das geniale an der Idee des Herrn Hollerith ist also, dass man die Anzahl der Eimer auf die Anzahl der verwendeten Symbole begrenzen und diese Eimer wiederholt benutzen kann. Würde man ein naives BucketSort oder CountingSort verwenden, so müßte man eintausend Eimer bereitstellen. Bei RadixSort braucht man nur zehn Eimer, die dafür drei mal. RadixSort ist also wesentlich übersichtlicher und, weil die Reihenfolge der Schichtungen immer beibehalten wird, auch stabil.

Da RadixSort stabil sortiert, werden auch geschachtelte Sortierungen sehr einfach. Will man etwa Rechnungen nach Datum und Kunden sortieren, dann sortiert man zunächst nach den Tagen, dann nach den Monaten, dann nach den Jahren und zum Schluß nach dem Kundennamen. Nach vier Sortierdurchgängen hat man die Kunden in alphabetischer Reihenfolge und von jedem Kunden die Rechnungen im zeitlichen Ablauf.

Da jede Position in jedem Schlüssel nur ein einziges mal betrachtet wird, ergibt sich die Gesamtzahl der Betrachtungen zu

A = n * d

wobei n die Anzahl der Datensätze ist und d die Anzahl der Zifferpositionen. Da die Bearbeitung jeder Zifferposition gleich lange dauert, steigt also der zeitliche Zuwachs von Sortierungen linear mit der Anzahl der zu sortierenden Datensätze.