Frage an algorithm, introsort, sorting – Wann wechselt Introsort von Quicksort zu Heapsort?

6

Introsort Beginnt mit Quicksort und wechselt zu Heapsort, wenn die Rekursionstiefe eine Ebene überschreitet, die auf der Anzahl der zu sortierenden Elemente basiert. Was ist diese Nummer? Gibt es einen bestimmten Bereich oder einen Grenzwert?

Deine Antwort

2   die antwort
2

Wikipedia-Artikel. Es sagt

Es zählt die Rekursionstiefe. Wenn eine logarithmische Tiefe überschritten wird, wechselt der Algorithmus von Quicksort zu Heapsort, um den ungünstigsten Fall von Quicksort zu vermeiden

und durch die Originalarbeit von Musser über Introsort.

Introsort ist langsamer als Heapsort, da es 2 * log (2, N) -Berechnungen durchführt, bevor es auf Heapsort umschaltet.

Mein Verständnis ist, dass die Rekursionstiefe 2 * log (2, N) ist.

Wenn N = 300 Elemente sortiert werden sollen, ist dies 2 * 8 = 16

Wenn Sie die Tiefenbeschränkung von 16 für eine Arry von 300 Elementen in ungefähr der 10. Tiefenebene verwenden, hat das Subarray 0 Elemente. this
6

Introsort-Algorithmus wechselt von Quicksort nach Heapsort wird bestimmt durchdepth_limit:

depth_limit = 2 · Log2(l) ⎦

Woherl ist die Länge der Sequenz, die sortiert werden soll, alsol‍ = ‍n für die gesamte Sequenz. Bei jedem rekursiven Aufrufdepth_limit wird um eins dekrementiert. Wanndepth_limit 0 erreicht, wechselt es von Quicksort nach Heapsort.

Nach Ihrer Logik wird der Heapsort niemals passieren, da die Tiefenbegrenzung niemals erreicht wird. this
Lesen Sie meinen Kommentar unten; Ein weiteres Beispiel: Ein Array mit 10000 Elementen hätte eine Tiefenbeschränkung von (13 * 2). Wenn das Array bei jeder Rekursion ungefähr in zwei Hälften geteilt wird, haben die Unterarrays auf der 14. Ebene 0 Elemente. this
@selbst. Nun, das Aufteilen in zwei Hälften ist der beste Fall. im schlimmsten Fall wird die Sequenz in (1, N-1) aufgeteilt. In diesem Fall erreicht depth_limit 0. Gumbo
@selbst. Warum denkst du das? Gumbo

Verwandte Fragen