Counting Sort und Radix Sort

Kurz: Counting Sort und Radix Sort sortieren ohne Vergleiche und können deshalb schneller sein als O(n log n), wenn die Schlüssel ganze Zahlen aus einem kleinen Bereich sind.

Genauer: Vergleichsbasierte Verfahren wie Quicksort können nie besser als O(n log n) sein. Wer Eigenschaften der Schlüssel ausnutzt, umgeht diese Grenze.

Im Detail

• Counting Sort: Zählt, wie oft jeder Wert vorkommt (Feld der Größe k), bildet daraus Anfangspositionen und schreibt die Elemente dorthin. Laufzeit O(n + k), stabil.
• Grenze: Ist der Wertebereich k riesig (zum Beispiel 64-Bit-Zahlen), ist das Zählfeld unbrauchbar.
• Radix Sort: Sortiert stellenweise, von der niedrigsten Stelle zur höchsten, jeweils mit einem stabilen Verfahren wie Counting Sort. Laufzeit O(d · (n + b)) bei d Stellen und Basis b.
• Beispiel: 32-Bit-Zahlen mit Basis 256: nur vier Durchgänge.
• Einsatz: Sortieren von IDs, Postleitzahlen, Zeichenketten fester Länge, Grafikpipelines.
• Preis: Zusatzspeicher und eine Bindung an die Schlüsselart.

Siehe auch: O-Notation, Sortieren