imported>Ot: Änderungen von 45.133.188.133 (Diskussion) auf die letzte Version von 80.155.12.250 zurückgesetzt

2022-05-24T09:03:47Z

Änderungen von 45.133.188.133 (Diskussion) auf die letzte Version von 80.155.12.250 zurückgesetzt

Neue Seite

'''Introsort''' ist ein [[Sortierverfahren|Sortieralgorithmus]]. Der Begriff ist eine Kurzform für „introspektives Sortieren“.
Der Algorithmus ist eine Variation von [[Quicksort]], welche in [[Entartung (Informatik)|entarteten]] Fällen auf ein anderes Sortierverfahren mit [[Worst-Case-Laufzeit]] [[O-Notation|<math> \Omega(n \log n) </math>]] (zum Beispiel [[Heapsort]]) zurückfällt.
Dazu wird zu Beginn jedes [[Rekursion]]sschrittes 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 <math display="inline"> \mathcal{O}(n \log n) </math> worst-case Zeitkomplexität gekoppelt (gegenüber <math display="inline"> \mathcal{O}(n^2) </math> 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 [[GNU Compiler Collection|GCC]].

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

== Weblinks ==
* [http://www.sgi.com/tech/stl/sort.html Introsort] in der [[Standard Template Library]] von [[Silicon Graphics|Silicon Graphics International]]
* [https://web.archive.org/web/20160304205301/http://home.arcor.de/delphi-server/sta_ralphunden_introsort.pdf ''Implementierung und Untersuchung des introspektiven Sortieralgorithmus Introsort.''] Studienarbeit an der BA Stuttgart von Ralph Unden (PDF; 328 kB)

[[Kategorie:Sortieralgorithmus]]

Introsort - Versionsgeschichte

imported>Ot: Änderungen von 45.133.188.133 (Diskussion) auf die letzte Version von 80.155.12.250 zurückgesetzt