Introsort
Quick Sort mit Tiefen-Limit, fällt bei zu tiefer Rekursion auf Heap Sort zurück.
- Vergleiche 0
- Tauschvorgänge 0
- sortierte Indizes 0
- Vergleich
- Tausch
- sortiert
Pseudocode
1 maxDepth = 2 * floor(log2(n))
2 introsort(0, n - 1, maxDepth)
3
4 introsort(lo, hi, depth):
5 if lo >= hi: return
6 if hi - lo < 16:
7 insertionSort(lo, hi); return
8 if depth == 0:
9 heapsort(lo, hi); return
10 p = partition(lo, hi)
11 introsort(lo, p - 1, depth - 1)
12 introsort(p + 1, hi, depth - 1)
13
14 insertionSort(lo, hi):
15 for i from lo + 1 to hi
16 key = a[i]; j = i - 1
17 while j >= lo and a[j] > key
18 a[j + 1] = a[j]; j = j - 1
19 a[j + 1] = key
20
21 partition(lo, hi):
22 pivot = a[hi]; i = lo - 1
23 for j from lo to hi - 1
24 if a[j] <= pivot: i++; swap a[i], a[j]
25 swap a[i + 1], a[hi]
26 return i + 1
27
28 heapsort(lo, hi):
29 size = hi - lo + 1
30 for k from size/2 - 1 downto 0: heapify(lo, hi, lo + k)
31 for end from hi downto lo + 1
32 swap a[lo], a[end]; heapify(lo, end - 1, lo)
33
34 heapify(lo, hi, root):
35 r = root - lo; l = 2r + 1; rr = 2r + 2; largest = root
36 if l < size and a[lo+l] > a[largest]: largest = lo + l
37 if rr < size and a[lo+rr] > a[largest]: largest = lo + rr
38 if largest != root:
39 swap a[root], a[largest]; heapify(lo, hi, largest)
Schritt-Log
Funktionsweise, Laufzeit und Speicher
Introsort (Introspective Sort) löst das pathologische Worst-Case-Verhalten von Quick Sort, das bei ungünstiger Pivot-Wahl in eine O(n²)-Laufzeit fallen kann. Der Algorithmus startet mit klassischem Quick Sort, beobachtet aber die Rekursionstiefe. Sobald diese das Limit von 2 · ⌊log₂(n)⌋ überschreitet, schaltet er auf Heap Sort um, der garantiert in O(n log n) bleibt. Sehr kleine Teilbereiche (typisch ≤ 16 Elemente) sortiert er mit Insertion Sort, weil dieser auf kleinen Eingaben sehr schnell ist. Damit hat Introsort die Average-Case-Schnelligkeit von Quick Sort, den garantierten O(n log n) Worst Case von Heap Sort und die Konstanten-Vorteile von Insertion Sort auf kleinen Bereichen. Der Speicherbedarf ist O(log n) für den Rekursions-Stack, und der Algorithmus ist nicht stabil.
Komplexität
- Best Case
O(n log n) - Average Case
O(n log n) - Worst Case
O(n log n) - Zusatz-Speicher
O(log n)
Wann verwenden?
Standard-Sortier-Algorithmus in der C++-STL (std::sort) seit dem C++11-Standard. Erste Wahl, wenn ein generischer, schneller in-place Sortier-Algorithmus mit garantierter O(n log n) Worst-Case-Laufzeit benötigt wird.