Introsort
aus Wikipedia, der freien Enzyklopädie
Introsort ist ein Sortieralgorithmus. Der Begriff ist eine Kurzform für "introspektives Sortieren". Der Algorithmus ist eine Variation von Quicksort, welche in entarteten Fällen auf ein anderes Sortierverfahren mit Worst-Case-Laufzeit O(n log n) (z. B. Heapsort) zurückfällt. Dazu wird zu Beginn jedes Rekursionsschrittes anhand einer Bewertungsfunktion entschieden, ob ein anderer Algorithmus für die Sortierung der Teilliste verwendet werden soll (z.B. bei Erreichen einer bestimmten Rekursionstiefe).
Auf diese Weise wird die Geschwindigkeit von Quicksort mit einer Worst-Case-Zeitkomplexität von O(n log n) gekoppelt.
Bekannt geworden ist Introsort vor allem dadurch, dass Silicon Graphics in seiner Standard Template Library für C++ seit einigen Jahren auf Introsort statt Quicksort zurückgreift. Inzwischen wurde Introsort auch in andere Implementierungen der Standard Template Library übernommen, unter anderem in die des GCC. Derzeit gilt Introsort als schnellstes instabiles Sortierverfahren.
[Bearbeiten] Literatur
- D. R. Musser: Introspective Sorting and Selection Algorithms. Software Practice and Experience 27(8):983, 1997
