Quicksort

Wählt einen Wert, das Pivotelement, und bringt kleinere Werte auf seine linke Seite, größere auf die rechte. Dann macht es dasselbe mit jeder Seite.

bester Fall Ω(n log n)
Durchschnitt Θ(n log n)
schlechtester Fall O(n²)
Speicher O(log n)
nicht stabil
ohne Zusatzspeicher

Was bedeutet das?

Bester Fall: wie die Zeit mit der Listengröße n wächst, wenn die Eingabe für diesen Algorithmus am einfachsten ist.
Durchschnitt: das übliche Wachstum der Zeit mit n. Bei n² dauern doppelt so viele Werte etwa viermal so lang. n log n wächst viel langsamer.
Schlechtester Fall: das Wachstum bei der schwierigsten Eingabe. Wichtig, wenn das Tempo nie einbrechen darf.
Speicher: wie viel Zusatzspeicher neben der Liste nötig ist. 1 heißt ein paar Variablen, n heißt eine Kopie der Liste.
Stabil: Zwei gleiche Werte behalten ihre ursprüngliche Reihenfolge. Wichtig, wenn man Datensätze nach einem Feld sortiert.
Ohne Zusatzspeicher: sortiert direkt in der Liste, ohne zweite Liste.

wird verglichen
wird verschoben
Pivotelement
am endgültigen Platz

0 / 187 Schritte

Vergleiche Tauschvorgänge

Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen

Geschwindigkeit 8 Schritte / s

Leertaste: abspielen oder pausieren. Pfeiltasten links/rechts: Schritt. Pos1 und Ende: springen.

Probieren Sie es aus: Wählen Sie eine umgekehrte Liste. Das Pivotelement ist immer der kleinste oder größte Restwert, daher wächst der Aufwand auf n².

So funktioniert es

Hier ist das Pivotelement der letzte Wert im Bereich. Von links nach rechts kommt jeder Wert, der nicht größer als das Pivotelement ist, per Tausch auf die linke Seite. Dann kommt das Pivotelement zwischen die beiden Seiten und bleibt dort. Jede Seite wird danach genauso sortiert.

Wann es sich eignet

In der Praxis eines der schnellsten Sortierverfahren, und es braucht kaum Zusatzspeicher. Wählt es aber immer wieder ein schlechtes Pivotelement, etwa bei einer schon sortierten Liste, wird es langsam. Echte Versionen wählen das Pivotelement deshalb sorgfältiger.