Introsort

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 $\Omega (n\log n)$ (zum Beispiel 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 (zum Beispiel bei Erreichen einer bestimmten Rekursionstiefe).

Auf diese Weise wird die Geschwindigkeit von Quicksort mit einer ${\textstyle {\mathcal {O}}(n\log n)}$ worst-case Zeitkomplexität gekoppelt (gegenüber ${\textstyle {\mathcal {O}}(n^{2})}$ bei reinem Quicksort). Die exakte Laufzeit ist in den entarteten Fällen etwas höher als bei direkter Anwendung des optimalen Algorithmus, da bis zum Rückfall auf das alternative Sortierverfahren Quicksort durchlaufen wird.

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 C++ Standard Library übernommen, unter anderem in die der GCC.

Literatur

David R. Musser: Introspective Sorting and Selection Algorithms. Software Practice and Experience 27(8): 983, 1997

Weblinks

Introsort in der Standard Template Library von Silicon Graphics International
Implementierung und Untersuchung des introspektiven Sortieralgorithmus Introsort. Studienarbeit an der BA Stuttgart von Ralph Unden (PDF; 328 kB)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.