Interaktive Demo
Introsort-Visualisierung
Introsort, 1997 von David Musser vorgestellt, beginnt als Quicksort, behält aber seine Rekursionstiefe im Blick. Gerät Quicksort an einen schlechten Fall, wechselt er zu Heapsort und braucht so nie mehr als n log n Schritte. Viele Standardbibliotheken nutzen ihn, etwa std::sort im C++-Compiler GCC.
Wähle „Schwerer Fall für Quicksort“: Der Median aus 3 spaltet immer wieder kleine Teile ab, bis das Tiefenlimit an Heapsort übergibt.
Ablauf
- Vergleiche
- 0
- Schreibzugriffe
- 0
Array
Legende
- Element
- Pivot · einsortiertes Element
- Pfeil „kleiner“ · größeres Kind
- Pfeil „größer“ · verglichenes Kind
- Endgültige Position
Laufzeit und Eigenschaften
Bester Fall
O(n log n)
Gute Pivots teilen jeden Abschnitt in der Mitte, wie bei Quicksort.
Mittlerer Fall
O(n log n)
Bei den meisten Eingaben ist er einfach Quicksort mit Median-aus-3-Pivot.
Schlechtester Fall
O(n log n)
Ist das Tiefenlimit erreicht, sortiert Heapsort den Teil in n log n fertig.
Zusätzlicher Speicher
O(log n)
Nur der Rekursionsstapel, höchstens so tief wie das Tiefenlimit.
Stabil
Nein
Vertauschungen von Quicksort und Heapsort können die Reihenfolge gleicher Elemente ändern.
In-place
Ja
Jeder seiner Teile sortiert innerhalb des Arrays.
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 | O(n log n) | O(n log n) | O(n²) | O(log n) | Nein | Ja |
| Introsort diese Seite | 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. Quicksort mit Tiefenlimit
Introsort partitioniert wie Quicksort, mit dem Median aus erstem, mittlerem und letztem Element als Pivot. Jede Rekursionsebene zählt auf ein Tiefenlimit, meist 2 · log₂ n.
2. Heapsort als Sicherheitsnetz
Erreicht ein Teil das Tiefenlimit, waren die Pivots schlecht und Quicksort könnte n² Schritte brauchen. Introsort sortiert diesen Teil dann mit Heapsort, der immer n log n Schritte braucht.
3. Hier vereinfacht
Damit alle drei Verfahren schon bei 11 Elementen zu sehen sind, ist das Tiefenlimit hier log₂ n statt 2 · log₂ n, und Teile mit bis zu 3 Elementen werden mit Insertion Sort sortiert (meist bis zu 16).