- Aktives Fach
- Gerade verschoben
- Zurückkopiert
- Platziert
Radixsort
Radixsort sortiert ganze Zahlen, ohne je zwei davon zu vergleichen. Es sortiert die Liste nach der Einerziffer, dann nach der Zehnerziffer, dann nach der Hunderterziffer, verschiebt die Werte dabei jedes Mal in zehn Fächer und kopiert sie der Reihe nach zurück. Sehen Sie zu, wie sich die Fächer in der Zeile unter der Liste füllen, eine Verschiebung nach der anderen, und wie die Liste nach immer mehr Ziffern sortiert wird. Drücken Sie „Abspielen“, um die Sortierung anzusehen, oder gehen Sie mit „Schritt“ und „Zurück“ eine Verschiebung nach der anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle zu springen. Die Fächer 0 bis 9 stehen nebeneinander in der Zeile unter der Liste. Die Kacheln zählen gelesene Ziffern, Verschiebungen und Durchläufe. Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene Zahlen bis 999 ein. Ist das Feld ausgewählt, gehen die Pfeiltasten schrittweise vor, die Leertaste startet und pausiert, und Pos1 und Ende springen zum Anfang und zum Ende.
Wie es funktioniert
- Wählen Sie die Anzahl der Balken und ihre Startreihenfolge, oder geben Sie eigene ganze Zahlen bis 999 ein, um den Durchlauf für die Hunderter zu sehen.
- Drücken Sie „Abspielen“ oder gehen Sie mit „Schritt“ und „Zurück“ einen Wert nach dem anderen durch. Ziehen Sie den Schrittregler, um an eine beliebige Stelle der Sortierung zu springen.
- Verfolgen Sie jeden Durchlauf: Ziffern zählen, jeden Wert in sein Fach verschieben, dann die Fächer zurückkopieren.
So funktioniert Radixsort
Betrachten Sie nur die letzte Ziffer jeder Zahl und sortieren Sie die Liste danach: Legen Sie jede Zahl in eines von zehn Fächern, 0 bis 9, in der Reihenfolge, in der die Zahlen kommen, und kopieren Sie die Fächer dann nacheinander zurück. Machen Sie dasselbe mit der Zehnerziffer, dann mit der Hunderterziffer. Weil jeder Durchlauf die Reihenfolge von Zahlen mit gleicher Ziffer beibehält, bestimmen die früheren Durchläufe weiter deren Reihenfolge, und nach dem letzten Durchlauf ist die ganze Liste sortiert.
Ganz ohne Vergleiche
Vergleichsbasierte Sortierverfahren brauchen im schlimmsten Fall mindestens etwa n log₂ n Vergleiche, egal welchen Trick sie nutzen. Radixsort umgeht diese Grenze, indem es stattdessen Ziffern liest: Jeder Durchlauf liest eine Ziffer jedes Werts und verschiebt jeden Wert zweimal, also brauchen d Ziffern d Durchläufe, und der Aufwand wächst mit n · d. Bei langen Listen kurzer Schlüssel lohnt sich das: Eine Million Zahlen bis 999 brauchen drei Durchläufe, wo ein vergleichsbasiertes Verfahren rund 20 Millionen Vergleiche braucht. Der Preis: Es funktioniert nur mit Schlüsseln aus Ziffern oder Zeichen und braucht Platz für die Fächer.
Häufig gestellte Fragen
Wie funktioniert Radixsort?
Es sortiert die Zahlen nach ihrer letzten Ziffer, dann nach der Ziffer davor und so weiter bis zur ersten Ziffer. Jeder Durchlauf verteilt die Zahlen nach dieser Ziffer auf zehn Fächer, ohne ihre Reihenfolge zu ändern, und kopiert die Fächer zurück. Nach dem Durchlauf für die höchstwertige Ziffer ist die Liste sortiert.
Warum mit der letzten Ziffer beginnen?
Weil jeder Durchlauf stabil ist: Zahlen mit gleicher Ziffer behalten die Reihenfolge, die ihnen die früheren Durchläufe gegeben haben. So entscheidet der letzte Durchlauf, über die erste Ziffer, die Reihenfolge, und bei Gleichstand entscheiden die schon sortierten Ziffern. Das nennt man LSD-Radixsort (least significant digit, niedrigstwertige Ziffer).
Ist Radixsort schneller als Quicksort?
Bei vielen kurzen Schlüsseln kann es das sein: Sein Aufwand wächst mit der Zahl der Werte mal der Zahl der Ziffern, ohne n log n. Bei wenigen Werten, sehr langen Schlüsseln oder Daten, die nicht aus Ziffern bestehen, sind Quicksort und Mergesort meist schneller und einfacher.
Wie hängt es mit Countingsort zusammen?
Jeder Durchlauf von Radixsort ist ein Countingsort auf einer Ziffer: zählen, wie viele Werte jede Ziffer haben, ausrechnen, wo jedes Fach beginnt, und die Werte der Reihe nach dorthin verschieben.
Werden meine Zahlen irgendwohin gesendet?
Nein. Die Sortierung läuft in Ihrem Browser, und Ihre letzten Einstellungen bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor