Quicksort verstehen – mit JavaScript-Beispielen

Quicksort ist ein Sortieralgorithmus nach dem Teile-und-herrsche-Prinzip: Er wählt ein Pivot-Element, partitioniert das Array so, dass kleinere Elemente nach links und größere nach rechts wandern, und sortiert anschließend jede Seite rekursiv – und zwar in place.

Die meisten von uns begegnen ihm zum ersten Mal am Whiteboard, während jemand zuschaut – und genau in der Partitionsschleife schwindet dann typischerweise das Selbstvertrauen. Der Algorithmus läuft im Durchschnitt in O(n log n), sortiert ohne ein zweites Array zu allokieren und ist der Algorithmus, zu dem die meisten Interviewer greifen, wenn sie Sie bitten, „das mal von Hand zu sortieren“.

Dieser Artikel behandelt drei Dinge: eine gut lesbare Variante zum Aufbau der Intuition, einen von Hand nachvollzogenen Partitionsdurchlauf, damit Sie die Elemente tatsächlich wandern sehen, und die In-place-Implementierung, die Sie in einem Interview wirklich schreiben würden – dazu Anmerkungen zu Komplexität, Pivot-Wahl und Stabilität.

Wie funktioniert der Quicksort-Algorithmus?

Quicksort sortiert, indem es das Array wiederholt um ein gewähltes Pivot-Element herum aufteilt. Ein Partitionsdurchlauf ordnet die Elemente so um, dass alles, was kleiner als das Pivot ist, davor liegt und alles Größere dahinter; das Pivot befindet sich danach an seiner endgültigen sortierten Position. Wendet man denselben Schritt auf den linken und rechten Teilbereich an, sortiert sich das gesamte Array von selbst.

Quicksort teilt die Teile-und-herrsche-Struktur mit Merge Sort, doch die Kompromisse unterscheiden sich. Beide, Quicksort und Merge Sort, liegen im Durchschnitt bei O(n log n), aber Quicksort sortiert in place mit O(log n) Hilfsspeicher, während Merge Sort O(n) zusätzlichen Speicher benötigt; zudem ist Merge Sort stabil, Quicksort nicht. Quicksort tauscht diese garantierte Stabilität gegen geringeren Speicherbedarf und hohe Geschwindigkeit in der Praxis.

Zuerst die gut lesbare Variante (filter und Spread)

Das am leichtesten lesbare Quicksort partitioniert mit filter und baut das Array mit dem Spread-Operator neu auf. Das ist der schnellste Weg, die Rekursion zu verstehen, und ein gutes Lehrmittel – aber bei jedem Aufruf werden neue Arrays allokiert, es arbeitet also nicht wirklich in place und verbraucht zusätzlichen Speicher.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

Der Basisfall (length <= 1) beendet die Rekursion, denn ein Array mit null oder einem Element ist bereits sortiert. Jeder Aufruf erzeugt drei neue Arrays, sodass der Speicherverbrauch dieser Variante mit der Eingabegröße wächst statt konstant zu bleiben. Nutzen Sie sie, um die Idee zu erklären; greifen Sie zur In-place-Variante weiter unten, wenn Speicherverbrauch oder Erwartungen im Interview eine Rolle spielen.

Wie funktioniert das Partitionieren?

Das Partitionieren ist der Motor von Quicksort – es lohnt sich also, einen Durchlauf genau zu beobachten. Das Lomuto-Schema nimmt das letzte Element als Pivot, führt einen Scan-Index j über den Bereich und hält einen Grenzindex i, der markiert, wohin das nächste Element „kleiner als das Pivot“ gehört. Immer wenn arr[j] kleiner als das Pivot ist, werden arr[i] und arr[j] getauscht und i weitergerückt. Am Ende wird das Pivot an Position i getauscht.

Verfolgen wir [7, 2, 1, 8, 6, 3, 5, 4] mit dem Pivot 4 (dem letzten Element), beginnend mit i = 0:

Das Pivot 4 landet an Index 3, mit [2,1,3] links und [6,7,5,8] rechts davon. Keine der beiden Seiten ist bereits sortiert, aber das Pivot ist endgültig platziert, und die beiden Seiten sind nun unabhängige Teilprobleme.

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

Das In-place-Quicksort, das Sie im Interview schreiben würden

Das produktionsnahe Quicksort behält den obigen Partitions-Helper und rekursiert über Indexbereiche (lo, hi), anstatt neue Arrays zu erzeugen. Zu dieser Variante sollten Sie greifen, wenn Sie jemand bittet, Quicksort zu implementieren: Sie verändert ein einzelnes Array und benötigt zusätzlichen Speicher nur für den Rekursionsstack.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

Jeder Aufruf partitioniert seinen Bereich und rekursiert dann über die beiden Teilbereiche links und rechts des Pivots. Die Bedingung lo < hi ist der Basisfall: Ein Bereich mit null oder einem Element ist bereits sortiert. Wenn Rekursion nicht erlaubt ist (eine häufige Anschlussfrage im Interview), lässt sich dieselbe Logik in eine iterative Variante überführen, indem man lo/hi-Paare auf einen expliziten Stack legt anstatt auf den Call Stack.

Komplexität, Pivot-Wahl und Stabilität

Die Kosten von Quicksort entscheiden sich fast vollständig am Pivot. Bei ausbalancierten Aufteilungen berührt jede Rekursionsebene jedes Element einmal, verteilt über etwa log n Ebenen – das ergibt O(n log n). Sind die Aufteilungen dagegen durchgängig einseitig, wächst die Rekursionstiefe auf n und die Kosten verschlechtern sich auf O(n²). Bei In-place-Umsetzung benötigt der Rekursionsstack bei ausbalancierten Eingaben O(log n) Speicher.

Die klassische Falle: Wählt man das erste oder letzte Element als Pivot, gerät Quicksort bei bereits sortierten Eingaben in seinen Worst Case von O(n²), weil jede Partition nur ein einziges Element abtrennt. Diesen Worst Case bei sortierten Eingaben vermeidet man, indem man das mittlere Element wählt, Median-of-Three verwendet oder ein zufälliges Pivot nimmt. Median-of-Three ordnet das erste, mittlere und letzte Element und verwendet den Median, was sowohl gegen sortierte als auch gegen umgekehrt sortierte, gezielt „bösartige“ Eingaben robust ist:

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

Eine Eigenschaft lässt sich mit keiner Pivot-Strategie zurückgewinnen: Quicksort ist kein stabiles Sortierverfahren, gleiche Elemente können also relativ zu ihren ursprünglichen Positionen vertauscht werden. Das ist relevant, wenn Sie Datensätze nach einem Sekundärschlüssel sortieren und erwarten, dass die primäre Ordnung erhalten bleibt.

Ist JavaScripts eingebautes sort ein Quicksort?

Nein. Obwohl der Quicksort-Algorithmus instabil ist, ist JavaScripts eingebautes Array.prototype.sort seit ES2019, der zehnten Ausgabe des Sprachstandards, garantiert stabil. V8 sortiert Arrays seit v7.0 und Chrome 70 mit Timsort: einem Merge Sort, der bereits geordnete Teilfolgen („Runs“) ausnutzt und gleiche Elemente in der vorgefundenen Reihenfolge belässt. Alle anderen großen Engines sind durch die Spezifikation an dieselbe Stabilitätsanforderung gebunden. „Quicksort ist instabil“ beschreibt also den Algorithmus, nicht das eingebaute sort in irgendeinem modernen Browser.

Quicksort verdankt seinen Ruf einer knappen Partitionsschleife, der In-place-Arbeitsweise und einer durchschnittlichen Geschwindigkeit von O(n log n) – solange Sie das Pivot von den Rändern des Arrays fernhalten. Implementieren Sie die obige In-place-Variante mit Median-of-Three oder einem zufälligen Pivot, testen Sie sie gegen eine sortierte Eingabe, um sicherzustellen, dass sie nicht kollabiert, und Sie werden Quicksort jederzeit sowohl schreiben als auch seine Trade-offs erklären können.

FAQs

Wann sollte ich Quicksort statt Merge Sort verwenden?

Verwenden Sie Quicksort, wenn der Speicher begrenzt ist und Sie in place sortieren möchten, denn es benötigt nur O(log n) Hilfsspeicher für den Rekursionsstack, während Merge Sort ein zusätzliches Array der Größe O(n) braucht. Beide liegen im Durchschnitt bei O(n log n), aber Quicksort ist bei typischen Daten in der Praxis schneller. Wählen Sie Merge Sort, wenn Sie garantierte Stabilität oder einen garantierten Worst Case von O(n log n) benötigen, da Quicksort auf O(n hoch zwei) abfallen kann.

Warum erreicht Quicksort bei einem bereits sortierten Array O(n hoch zwei)?

Ein fest gewähltes erstes oder letztes Pivot verschlechtert sich bei sortierter Eingabe auf O(n hoch zwei), weil jede Partition das Pivot an ein Ende setzt und einen leeren Teilbereich sowie einen Bereich mit n minus 1 Elementen erzeugt. Das ergibt n Rekursionsebenen statt log n, wobei jede lineare Arbeit leistet. Die Lösung besteht darin, das mittlere Element zu wählen, Median-of-Three zu verwenden oder ein zufälliges Pivot zu nehmen – all das stellt bei sortierten Daten ausbalancierte Aufteilungen wieder her.

Ist JavaScripts Array.prototype.sort mit Quicksort implementiert?

Nein. Moderne Engines verwenden für das eingebaute sort kein Quicksort. V8 nutzt seit v7.0 und Chrome 70 Timsort, einen Merge Sort, der bereits geordnete Teilfolgen ausnutzt und die Reihenfolge gleicher Elemente bewahrt. Seit ES2019 verlangt die ECMAScript-Spezifikation, dass Array.prototype.sort stabil ist, und jede große Engine liefert ein stabiles Sortierverfahren aus. Der Algorithmus Quicksort ist also instabil, aber das eingebaute sort ist kein Quicksort und ist garantiert stabil.

Was ist der Unterschied zwischen dem Lomuto- und dem Hoare-Partitionsschema?

Lomuto verwendet einen einzelnen Scan-Index und nimmt typischerweise das letzte Element als Pivot, wobei kleinere Elemente in Richtung eines Grenzindex getauscht werden; es ist einfacher zu schreiben und nachzuvollziehen. Hoare verwendet zwei Zeiger, die sich von beiden Enden nach innen bewegen, und führt in der Regel weniger Vertauschungen durch, was es in der Praxis schneller macht. Beide partitionieren in place und geben einen Teilungspunkt zurück, aber der von Hoare zurückgegebene Index platziert das Pivot nicht an seiner endgültigen Position, so wie es bei Lomuto der Fall ist.

Wie wandle ich rekursives Quicksort in eine iterative Variante um?

Ersetzen Sie den Call Stack durch einen expliziten Stack von Indexbereichen. Legen Sie das initiale lo-hi-Paar ab und schleifen Sie, solange der Stack nicht leer ist: Nehmen Sie einen Bereich vom Stack, partitionieren Sie ihn, um einen Pivot-Index p zu erhalten, und legen Sie die beiden Teilbereiche lo bis p minus 1 sowie p plus 1 bis hi wieder auf den Stack, wenn sie mehr als ein Element enthalten. Das liefert dasselbe Ergebnis ohne Rekursion – eine häufige Anschlussfrage im Interview.