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.

Wichtige Eigenschaften:

• Nicht-vergleichend: Radixsort vergleicht keine Elemente direkt miteinander, sondern nutzt die Ziffernpositionen.
• Bei entsprechender Implementierung ist Radixsort stabil: Die Reihenfolge gleichwertiger Elemente bleibt wie in der Ausgangsliste erhalten.
• Laufzeit: Die Zeitkomplexität beträgt im Allgemeinen O(k·(b+n)), wobei k die maximale Schlüssellänge (Anzahl der Ziffern), b die Basis (z.B. 10 bei Dezimalzahlen) und n die Anzahl der zu sortierenden Elemente ist
• Radixsort ist besonders effizient, wenn die Anzahl der Ziffern (bzw. die Schlüssellänge) im Vergleich zur Anzahl der Elemente klein ist