Warum verwendet Introsort Heapsort anstelle von Mergesort?

Im Rahmen einer Hausaufgabe zur Implementierung von Introsort werde ich gefragt, warum Heapsort anstelle von Mergesort (oder anderen -Algorithmen) verwendet wird. $O(n\log(n))$

Introsort ist ein hybrider Sortieralgorithmus, der sowohl eine schnelle Durchschnittsleistung als auch (asymptotisch) eine optimale Worst-Case-Leistung bietet. Es beginnt mit Quicksort und wechselt zu Heapsort, wenn die Rekursionstiefe eine Ebene überschreitet, die auf (dem Logarithmus von) der Anzahl der zu sortierenden Elemente basiert. ( Wikipedia , abgerufen am 06. Mai 2014)

Der einzige Grund, an den ich denken kann, ist, dass Heapsort "an Ort und Stelle" ist ... Aber ich verstehe nicht wirklich, warum dies hier wichtig sein würde.

algorithms algorithm-analysis sorting user672009
quelle

Wenn Introsort Teil der Frage ist, müssen Sie uns sagen, was es ist, bevor wir etwas sagen können.

Louis

Willkommen in der Informatik ! Beachten Sie, dass Sie hier LaTeX verwenden können, um die Mathematik besser lesbar zu setzen. Sehen Sie hier eine kurze Einführung.

FrankW

Wir werden einfach gebeten, einen Pseudocode für die Intro-Sortierung zu erstellen, und später werden wir gefragt, warum Heapsort anstelle von Mergesort verwendet wird.

user672009

@ user672009 In diesem Fall schreiben Sie den Code für beide auf und sehen Sie, was Sie finden. Der Grund kann mit der Leistung zusammenhängen oder nicht.

Raphael

Ich bin zu dem Schluss gekommen, dass wir, da Quicksort-Sortierungen vorhanden sind, einen anderen Sortieralgorithmus an Ort und Stelle verwenden müssen. Ich bin jedoch offen für Beiträge.

user672009

Antworten:

Die 2 Nachteile von Quicksort sind, dass zusätzlichen Speicherplatz benötigt (um die unsortierten Intervalle beizubehalten) und eine schlechte Pivot-Auswahl (oder erfundene Sequenzen, mit denen Sie einen schlechten Pivot auswählen können) dazu führen kann, dass es sich um ein Zeit und zusätzlicher Raumalgorithmus. $O(\log n)$ $O(n^2)$ $O(n)$

Das Umschalten auf Heapsort, wenn die Rekursionstiefe zu groß wird (um ), bedeutet, dass wir eine garantierte Obergrenze haben, die Zeit und zusätzlichen Speicherplatz ist. $\log n$ $O(n \log n )$ $O( \log n)$

Der zusätzliche Platzbedarf von Heapsort für macht es zu einer besseren Wahl, für Mergsort zusammenzuführen, wenn für ein erfundenes Array immer noch groß sein könnte. $O(1)$ $O(n)$ $n$

Der Grund, warum Heapsort nicht für die vollständige Sortierung verwendet wird, liegt darin, dass es langsamer als Quicksort ist (teilweise aufgrund der versteckten Konstanten im großen O-Ausdruck und teilweise aufgrund des Cache-Verhaltens).

Ratschenfreak
quelle

Aber Heapsort wird verwendet ... und ich vermute, es liegt daran, dass es wie Quicksort vorhanden ist.

user672009

Ich vermute, dass @ user672009 durch Ihren letzten Satz verwirrt ist. Ich würde klarstellen, dass Introsort nicht mit Heapsort beginnt, weil es langsamer ist.

Wandering Logic

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Darüber hinaus weist Heapsort viel mehr Cache-Fehler auf als Introsort.

noɥʇʎԀʎzɐɹƆ

Eine gute Quicksort-Implementierung benötigt im schlimmsten Fall keinen O (n) -Speicherplatz, solange sie sich an das größere Subintervall auf dem Stapel erinnert und das kleinere sofort verarbeitet.

Gnasher729