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.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- nein
- ja
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
Rekursionstiefe: 0 · mindestens möglich: 4 · schlimmstenfalls: 23 wartet auf sein Pivotelement
Auf Abspielen drücken: Die Linien zeigen, wie die Kosten wachsen
Auf Abspielen drücken oder Schritt für Schritt durchgehen.
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.