Radixsort

Radixsort ist unter den Sortierverfahren der Außenseiter: Es fragt nie, welcher von zwei Werten größer ist. Es liest die Zahlen Ziffer für Ziffer und sortiert sie nach jeweils einer Ziffer, mit zehn Fächern. Die Idee ist älter als der Computer: So arbeiteten die Sortiermaschinen für Lochkarten.

Balken einer Liste über einer Reihe von zehn Fächern mit den Beschriftungen 0 bis 9; ein Wert fällt in das Fach seiner letzten Ziffer
Balken einer Liste über einer Reihe von zehn Fächern mit den Beschriftungen 0 bis 9; ein Wert fällt in das Fach seiner letzten Ziffer

Die Idee

Sortieren Sie die Zahlen nur nach ihrer Einerziffer. Dann sortieren Sie sie nach ihrer Zehnerziffer, aber so, dass Zahlen mit gleicher Zehnerziffer in der Reihenfolge des ersten Durchlaufs bleiben. Dann ebenso nach der Hunderterziffer. Nach dem letzten Durchlauf ist die Liste sortiert: Die Hunderter entscheiden zuerst, bei gleichen Hundertern stehen die Zahlen schon nach ihren Zehnern geordnet, und bei gleichen Zehnern nach ihren Einern.

Ein Durchlauf mit Fächern

Jeder Durchlauf nutzt zehn Fächer, eines für jede Ziffer von 0 bis 9. Gehen Sie die Liste von vorn bis hinten durch und verschieben Sie jede Zahl in das Fach ihrer Ziffer, hinter die Zahlen, die schon dort liegen. Dann leeren Sie die Fächer der Reihe nach zurück in die Liste, Fach 0 zuerst. Dass die Zahlen in Listenreihenfolge verschoben und hinten an ein Fach angehängt werden, macht den Durchlauf stabil. Die App zählt zuerst die Zahlen für jede Ziffer, damit die Fächer nebeneinander in einer Zeile stehen können, jedes direkt nach dem vorigen: Das ist ein Countingsort auf einer Ziffer.

Ein Beispiel

Nehmen Sie 170, 45, 75, 90, 802, 24, 2, 66. Nach der Einerziffer: 170, 90, 802, 2, 24, 45, 75, 66. Nach der Zehnerziffer: 802, 2, 24, 45, 66, 170, 75, 90; dabei behalten 802 und 2, beide mit Zehnerziffer 0, ihre Reihenfolge aus dem ersten Durchlauf. Nach der Hunderterziffer: 2, 24, 45, 66, 75, 90, 170, 802. Drei Durchläufe über acht Zahlen: 24 gelesene Ziffern und 48 Verschiebungen, und kein einziger Vergleich.

Wie schnell ist es?

Jeder Durchlauf liest eine Ziffer jeder Zahl und verschiebt jede Zahl zweimal, also wächst der Aufwand für n Zahlen mit d Ziffern mit n · d. Ein vergleichsbasiertes Verfahren braucht im schlimmsten Fall mindestens etwa n log₂ n Vergleiche, weil es n! mögliche Reihenfolgen mit Ja-Nein-Fragen unterscheiden muss, eine nach der anderen. Radixsort ist daran nicht gebunden, da es solche Fragen nie stellt. Bei vielen kurzen Schlüsseln, etwa einer Million Zahlen unter 1.000, sind drei Durchläufe weit weniger Arbeit als die rund 20 Millionen Vergleiche eines vergleichsbasierten Verfahrens. Bei langen Schlüsseln oder wenigen Werten verschwindet der Vorteil.

LSD und MSD, und Geschichte

Die hier gezeigte Variante beginnt mit der niedrigstwertigen Ziffer (LSD). Umgekehrt, mit der höchstwertigen Ziffer zuerst (MSD), teilt man die Liste nach der ersten Ziffer in Fächer auf und sortiert jedes Fach einzeln; das passt zu Zeichenketten unterschiedlicher Länge. Radixsort geht auf die Lochkartensortierer zurück, die auf Herman Holleriths Tabelliermaschinen für die US-Volkszählung von 1890 folgten: Ein Sortierer ließ jede Karte nach dem Loch in einer Spalte in eines von zehn Fächern fallen, und das Personal ließ den Stapel einmal pro Spalte durchlaufen, beginnend mit der letzten.

Eine Hollerith-Lochkarten-Tabelliermaschine im Computer History Museum, von der Art, die bei der US-Volkszählung 1890 verwendet wurde. Die Bediener führten einen Stapel einmal pro Spalte durch einen Sorter – der Vorläufer von Radixsort.
Eine Hollerith-Lochkarten-Tabelliermaschine im Computer History Museum, von der Art, die bei der US-Volkszählung 1890 verwendet wurde. Die Bediener führten einen Stapel einmal pro Spalte durch einen Sorter – der Vorläufer von Radixsort.

Ausprobieren

Öffnen Sie die App und drücken Sie „Schritt“. Jeder Durchlauf zählt zuerst die Ziffern und steckt so die Fächer 0 bis 9 in der Zeile unter der Liste ab. Dann fallen die Zahlen eine nach der anderen in ihre Fächer, das aktive Fach hervorgehoben, und werden zurückkopiert. Geben Sie eigene Zahlen bis 999 ein, etwa das Beispiel oben, um alle drei Durchläufe zu sehen.

Häufig gestellte Fragen

Welche Zeitkomplexität hat Radixsort?

O(n · d) für n Schlüssel mit d Ziffern in einer festen Basis, plus die Kosten der Fächer in jedem Durchlauf. Es braucht O(n) zusätzlichen Speicher für den Puffer, in dem die Fächer liegen.

Ist Radixsort stabil?

LSD-Radixsort muss es sein: Es funktioniert nur, weil jeder Durchlauf Werte mit gleicher Ziffer in ihrer bisherigen Reihenfolge lässt. Daher ist auch das Endergebnis stabil.

Kann Radixsort negative Zahlen oder Dezimalzahlen sortieren?

Nicht direkt, aber mit einem Trick: Verschieben Sie negative Zahlen so, dass alle positiv sind, oder sortieren Sie sie getrennt und kehren Sie ihre Reihenfolge um. Gleitkommazahlen lassen sich nach einer kleinen Umwandlung nach ihren Bitmustern sortieren.

Warum Basis 10?

Weil sie leicht nachzuvollziehen ist. Computer sortieren meist nach 8 oder 16 Bit auf einmal, eine 32-Bit-Zahl braucht also vier oder zwei Durchläufe, mit 256 oder 65.536 Fächern.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Radixsort ausprobieren