Quicksort einfach erklärt: Ablauf und Laufzeit

Quicksort sortiert eine Liste, indem er sie wiederholt teilt. Zuerst wählt er ein Element als Pivotelement aus. In den Beispielen hier ist das Pivot das Element ganz rechts.

Dann wird die Liste geteilt (man sagt auch: partitioniert). Alle Elemente, die kleiner als das Pivot sind, kommen in die linke Teilliste, alle größeren in die rechte. Elemente, die gleich dem Pivot sind, können sich beliebig auf die Teillisten verteilen. Die Elemente werden dabei nur innerhalb der Liste vertauscht und nicht in zusätzlichen Speicher kopiert.

So teilst du, wenn das Pivot ganz rechts steht: Der Index i startet links und sucht ein Element, das größer als das Pivot ist. Der Index j startet auf dem Element vor dem Pivot und sucht von rechts ein Element, das kleiner oder gleich dem Pivot ist. Die beiden gefundenen Elemente tauschst du. Danach suchen beide von ihren Positionen aus weiter, bis sich die Suchen treffen. Dort ist die Grenze zwischen den Teillisten.

Am Ende tauschst du das Pivot mit dem Element bei i, falls dieses Element größer als das Pivot ist. Sonst bleibt das Pivot, wo es ist. Dann steht das Pivot an der Trennstelle. Links davon stehen nur Elemente kleiner oder gleich dem Pivot, rechts nur größere.

Zum Schluss wendest du dasselbe Verfahren auf die linke und auf die rechte Teilliste an. Diese Selbstaufrufe heißen Rekursion. Das echte Beispiel unten sortiert Buchstaben alphabetisch. Das Zahlenbeispiel in der Musteraufgabe ist von uns ausgedacht.

Quicksort arbeitet nach dem Prinzip „Teile und herrsche“: Er teilt die Liste und sortiert die Teile auf dieselbe Weise. Die Begründung, dass am Ende alles sortiert ist, besteht aus drei Schritten. Sie ist keine formale Beweisführung.

Erstens der Basisfall: Eine Teilliste der Länge eins oder null ist bereits sortiert. Dort bricht die Rekursion ab. Im Pseudocode wird nur geteilt, falls links < rechts gilt. Sonst passiert nichts.

Zweitens die Zerlegung: Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste. Das Pivot steht an seiner endgültigen Position, kleinere Elemente davor, größere danach. Der Pseudocode ruft quicksort(links, teiler - 1) und quicksort(teiler + 1, rechts) auf. Wenn beide Teillisten in sich sortiert sind, ist die Gesamtliste sortiert, weil die Teillisten schon in der richtigen Position liegen.

Drittens muss die Rekursion enden. Das ist nur dann garantiert, wenn jede Teilliste mindestens um eins kürzer ist als die Gesamtliste. Das lässt sich zum Beispiel erreichen, indem das Pivot zwischen die Teillisten gesetzt wird und so zu keiner Teilliste gehört. Dann endet die Rekursion nach endlich vielen Schritten.

Ein Beispiel: Beim Sortieren der Buchstabenfolge „Quicksort“ entsteht nach dem ersten Teilen Qricksotu. Das t steht an der Trennstelle, rechts davon steht nur das u. Das ist ein einzelnes Element und damit sortiert. Quicksort ist im Allgemeinen nicht stabil: Gleiche Elemente können nach dem Sortieren in anderer Reihenfolge stehen.

Die Laufzeit von Quicksort hängt im Wesentlichen von der Wahl des Pivotelements ab. Die Schreibweise O(…) nennt, wie die Zahl der Vergleiche bei n Elementen ausfällt. n ist die Länge der Liste.

Im besten Fall wird das Pivot so gewählt, dass die beiden Teillisten etwa gleich groß sind. Dann gilt für die Laufzeit O(n·log(n)). Dieselbe Zeitkomplexität gilt ebenso für den durchschnittlichen Fall. Die Tiefe der Rekursion, also wie viele Selbstaufrufe ineinander stecken, liegt dann im Durchschnitt in O(log(n)).

Im schlechtesten Fall ist das Pivot stets das größte oder das kleinste Element der Liste. Das passiert zum Beispiel, wenn stets das letzte Element Pivot ist und die Liste schon sortiert vorliegt. Die Liste wird dann in jedem Rekursionsschritt nur um eins kleiner. Es werden O(n²) Vergleiche durchgeführt. Das kommt in der Praxis aber sehr selten vor.

Zum Speicher: Quicksort vertauscht die Elemente nur innerhalb der Liste. Für jede Rekursionsebene braucht er aber zusätzlichen Platz auf dem Stack (dem Stapel, auf dem die laufenden Aufrufe liegen). Auch dieser Speicherverbrauch hängt von der Pivotwahl und den Daten ab. Im günstigsten und durchschnittlichen Fall ist der Stapel O(log(n)) groß. Im ungünstigsten Fall ist die Zahl der Rekursionen nur durch die Listenlänge n beschränkt. Dann ist der Stapel O(n) groß, und bei langen Listen kann ein Stapelüberlauf entstehen.

Eine Gegenmaßnahme: Wird bei jeder Teilung die kürzere Teilliste rekursiv sortiert und die längere iterativ weiterverarbeitet (also mit einer Schleife statt mit einem weiteren Selbstaufruf), ist die Rekursionstiefe nicht größer als log(n).