Introsort - LinkFang.de





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 [math] \mathcal{O}(n \log n) [/math] (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 [math] \mathcal{O}(n \log n) [/math]-Worst-Case-Zeitkomplexität gekoppelt (gegenüber [math] \Theta(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 GCC. Derzeit gilt Introsort als schnellstes instabiles Sortierverfahren.

Literatur

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

Weblinks


Kategorien: Sortieralgorithmus

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Introsort (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.