Radix Sort

Nicht-Vergleichsbasiert

Sortiert Ganzzahlen stelle für stelle von der niedrigsten zur höchsten Stelle — nutzt an jeder Stelle einen stabilen Algorithmus (Counting Sort).

Live-Visualisierung

Komplexität

Bester Fall	O(nk)
Durchschnitt	O(nk)
Schlechtester Fall	O(nk)
Speicherkomplexität	O(n + k)
Stabiles Sortieren	Ja
In-Place	Nein

Legende

O(1): Konstant: Egal wie viele Elemente — der Aufwand bleibt gleich.
O(n): Linear: Doppelt so viele Elemente → doppelt so viel Aufwand.
O(n log n): Quasi-Linear: Wenig schlechter als linear — der Goldstandard für Sortieren.
O(n²): Quadratisch: 10× mehr Elemente → 100× mehr Aufwand. Langsam bei großen Listen.
Stabil: Stabile Sortierung: Gleiche Werte behalten ihre ursprüngliche Reihenfolge zueinander.
In-Place: In-Place: Sortiert direkt im vorhandenen Speicher, ohne eine Kopie der Liste anzulegen.
Vergleichsbasiert: Vergleichsbasiert: Der Algorithmus entscheidet nur durch „ist A kleiner als B?" — funktioniert mit beliebigen Werten.
Nicht-Vergleichsbasiert: Nicht-Vergleichsbasiert: Nutzt die Struktur der Zahlen selbst (z. B. Ziffern) — kann dadurch schneller als O(n log n) sein.

Implementierung

TypeScript-Implementierung — direkt kopierbereit.

function radixSort(arr: number[]): number[] {
  const max = Math.max(...arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSortByDigit(arr, exp);
  }
  return arr;
}

function countingSortByDigit(arr: number[], exp: number): void {
  const n = arr.length;
  const output = new Array(n);
  const count = new Array(10).fill(0);

  for (let i = 0; i < n; i++) count[Math.floor(arr[i] / exp) % 10]++;
  for (let i = 1; i < 10; i++) count[i] += count[i - 1];
  for (let i = n - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[--count[digit]] = arr[i];
  }
  for (let i = 0; i < n; i++) arr[i] = output[i];
}

Wie es funktioniert

Radix Sort verarbeitet Zahlen stelle für stelle statt vollständige Werte zu vergleichen. Beginnend bei der niedrigstwertigen Stelle (LSD-Variante) gruppiert er Elemente nach dieser Stelle mit einem stabilen Sortierverfahren (Counting Sort) und wiederholt dies für jede höhere Stelle. Nach der Verarbeitung aller d Stellen ist das Array vollständig sortiert.

Warum LSD funktioniert: Da Counting Sort stabil ist, bewahren gleiche Ziffern an der aktuellen Stelle ihre relative Reihenfolge aus dem vorherigen Durchgang. Über alle Durchgänge hinweg entsteht so die korrekte Gesamtordnung.

Komplexität: O(nk), wobei k die Anzahl der Stellen ist (log₁₀(max)). Für 32-Bit-Ganzzahlen in Basis 256 (4 Durchgänge) ist dies effektiv O(4n) = O(n).

Wann verwenden: Große Arrays von Ganzzahlen oder gleichlangen Zeichenketten, wenn die Schlüssellänge k klein relativ zu n ist. Wird beim Aufbau von Suffix-Arrays und in manchen Datenbanksystemen eingesetzt.

Vergleiche Radix Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Counting Sort Tim Sort