Interaktive Demo
Quicksort-Visualisierung
Quicksort ist ein weit verbreiteter Sortieralgorithmus nach dem Prinzip „Teile und herrsche“. Er braucht im Durchschnitt O(n log n) Schritte und im schlechtesten Fall O(n²).
Klicke auf „Nächster Schritt“, um Schritt für Schritt vorzugehen, oder auf „Abspielen“, um den Algorithmus selbst laufen zu lassen. Probiere verschiedene Ausgangsreihenfolgen aus.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Unsortiertes Element
- Pivot
- Pfeil „kleiner“
- Pfeil „größer“
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Jedes Pivot teilt seinen Abschnitt in zwei gleich große Hälften.
Mittlerer Fall
O(n log n)
Im Mittel teilen die Pivots gut genug: etwa log n Ebenen mit je n Vergleichen.
Schlechtester Fall
O(n²)
Das Pivot ist immer das kleinste oder größte Element, jede Ebene entfernt also nur ein Element.
Zusätzlicher Speicher
O(log n)
Nur der Rekursionsstapel, solange der kleinere Teil zuerst sortiert wird.
Stabil
Nein
Vertauschungen über weite Strecken können die Reihenfolge gleicher Elemente ändern.
In-place
Ja
Elemente werden nur innerhalb des Arrays vertauscht.
n ist die Anzahl der Elemente. O(n log n) ist das Beste, was ein Sortierverfahren auf Basis von Vergleichen erreichen kann.
Im Vergleich mit den anderen Sortieralgorithmen
| Algorithmus | Bester Fall | Mittlerer Fall | Schlechtester Fall | Zusätzlicher Speicher | Stabil | In-place |
|---|---|---|---|---|---|---|
| Bubblesort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Selectionsort | O(n²) | O(n²) | O(n²) | O(1) | Nein | Ja |
| Insertionsort | O(n) | O(n²) | O(n²) | O(1) | Ja | Ja |
| Shellsort | O(n log n) | ≈ O(n1.25) | O(n1.5) | O(1) | Nein | Ja |
| Treesort | O(n log n) | O(n log n) | O(n²) | O(n) | Ja | Nein |
| Tournamentsort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Smoothsort | O(n) | O(n log n) | O(n log n) | O(1) | Nein | Ja |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Patiencesort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Blocksort | O(n) | O(n log n) | O(n log n) | O(1) | Ja | Ja |
| Quicksort diese Seite | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort | O(n log n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
| Fluxsort | O(n) | O(n log n) | O(n log n) | O(n) | Ja | Nein |
| Crumsort | O(n) | O(n log n) | O(n log n) | O(log n) | Nein | Ja |
1. Pivot wählen
Ein Element des aktuellen Abschnitts wird als Pivot gewählt und an das Ende dieses Abschnitts verschoben.
2. Aufteilen
Zwei Pfeile laufen aufeinander zu und tauschen Elemente, bis alle kleineren Werte links und alle größeren rechts vom Pivot liegen.
3. Rekursion
Das Pivot rückt an seine endgültige Position und wird als fertig markiert. Danach wiederholen sich die Schritte für den linken und den rechten Teil, bis das Array sortiert ist.