Radixsort

Radixsort ist ein nicht-vergleichender Sortieralgorithmus. Er funktioniert besonders gut beim Sortieren von Ganzzahlen, darum betrachten wir hier zunächst auch nur diesen Fall.

Radixsort sortiert die Elemente einer Liste, indem er sie nach einzelnen Ziffern (Stellenwerten) gruppiert, meistens beginnend mit der niederwertigsten Ziffer. Für jede Ziffer der zu sortierenden Zahlen wird ein sogenannter "Bucket" verwendet, in den die Zahlen einsortiert werden. Nachdem die Elemente auf die "Buckets" verteilt wurden, werden sie wieder eingesammelt, was dazu führt, dass die Sortierung für die betrachtete Stelle korrekt ist. Dieser Vorgang wird für die Ziffern jeder Stelle wiederholt, bis alle Stellen abgearbeitet sind, dann ist die Liste sortiert.

Mit den Hunderter/Tausender u.s.w. Stellen verfährt man dann ebenso, bis man die gesamte Länge der Elemente durchlaufen hat. Dann ist die Liste sortiert. |