Quick Sort

Vergleichsbasiert

Wählt einen Pivot, partitioniert das Array in Elemente kleiner und größer als der Pivot und sortiert jede Partition rekursiv.

Live-Visualisierung

Komplexität

Bester Fall	O(n log n)
Durchschnitt	O(n log n)
Schlechtester Fall	O(n²)
Speicherkomplexität	O(log n)
Stabiles Sortieren	Nein
In-Place	Ja

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 quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
  return arr;
}

function partition(arr: number[], low: number, high: number): number {
  // Median-of-Three Pivot-Auswahl
  const mid = Math.floor((low + high) / 2);
  if (arr[mid] < arr[low]) [arr[low], arr[mid]] = [arr[mid], arr[low]];
  if (arr[high] < arr[low]) [arr[low], arr[high]] = [arr[high], arr[low]];
  if (arr[mid] < arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]];
  const pivot = arr[high];
  let i = low - 1;
  for (let j = low; j < high; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
  return i + 1;
}

Wie es funktioniert

QuickSort ist der meistgenutzte Allzweck-Sortieralgorithmus. Er wählt ein „Pivot"-Element und ordnet das Array so um, dass alle kleineren Elemente vor dem Pivot stehen und alle größeren danach. Anschließend wird dieses Partitionierungsverfahren rekursiv auf jede Seite angewendet.

Pivot-Auswahl ist entscheidend: Naive Implementierungen, die das erste oder letzte Element als Pivot nehmen, degradieren bei bereits sortierten Arrays auf O(n²). Produktive Implementierungen verwenden Median-of-Three oder zufällige Pivot-Auswahl.

In-Place: Im Gegensatz zu Merge Sort partitioniert QuickSort direkt im Array mit nur O(log n) Stack-Speicher für die rekursiven Aufrufe.

Wann verwenden: Allgemeines Sortieren, bei dem die durchschnittliche Laufzeit entscheidend ist. In der Praxis der schnellste Algorithmus für zufällige Daten durch ausgezeichnetes Cache-Verhalten. Wird in C's qsort und V8's JavaScript-Engine verwendet.

Vergleiche Quick Sort direkt mit einem anderen Algorithmus

Code vergleichen →

Merge Sort Heap Sort