Counting Sort

Nicht-Vergleichsbasiert

Zählt das Vorkommen jedes Wertes und rekonstruiert daraus das sortierte Array — lineare Laufzeit, aber auf Integer-Schlüssel in einem begrenzten Bereich beschränkt.

Live-Visualisierung

Komplexität

Bester Fall	O(n + k)
Durchschnitt	O(n + k)
Schlechtester Fall	O(n + k)
Speicherkomplexität	O(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 countingSort(arr: number[]): number[] {
  if (arr.length === 0) return arr;
  const max = Math.max(...arr);
  const min = Math.min(...arr);
  const range = max - min + 1;
  const count = new Array(range).fill(0);
  const output = new Array(arr.length);

  // Vorkommen zählen
  for (const val of arr) count[val - min]++;

  // Kumulative Zählungen (Positionen)
  for (let i = 1; i < range; i++) count[i] += count[i - 1];

  // Ausgabe rückwärts aufbauen (für Stabilität)
  for (let i = arr.length - 1; i >= 0; i--) {
    output[--count[arr[i] - min]] = arr[i];
  }
  return output;
}

Wie es funktioniert

Counting Sort durchbricht die O(n log n)-Schranke vergleichsbasierter Sortierung, indem er Elemente gar nicht vergleicht. Er zählt, wie oft jeder ganzzahlige Wert in der Eingabe vorkommt, akkumuliert diese Zählungen zu Positionen und platziert jedes Element direkt an seine korrekte Ausgabeposition.

k = Wertebereich der Eingabe. Bei n Elementen im Bereich 0 bis k läuft der Algorithmus in O(n + k) Zeit und O(k) Speicher. Wenn k = O(n) ist, ergibt sich eine lineare Laufzeit.

Stabilität: Durch rückwärts iterierte Ausgabebefüllung behalten gleiche Elemente ihre ursprüngliche Reihenfolge — wichtig, wenn er als Unterroutine in Radix Sort eingesetzt wird.

Wann verwenden: Sortieren von Ganzzahlen in einem bekannten, begrenzten Bereich. Klassische Anwendung: Noten (0–100), Alterswerte (0–150) oder als innere Schleife von Radix Sort. Ungeeignet, wenn k >> n ist.

Vergleiche Counting Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Shell Sort Radix Sort