Wanneer verschuift de introsort van quicksort naar heapsort?

Introsort begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on the number of elements being sorted. What is that number? Is there a specific range or a limiting value?

5

2 antwoord

Het punt waarop het Introsort-algoritme overschakelt van Quicksort naar Heapsort wordt bepaald door Depth_limit :

depth_limit = 2 · ⎣log 2 ( l ) ⎦

Waar l de lengte van de reeks is die moet worden gesorteerd, dus l = n voor de hele reeks. Bij elk recursief gesprek wordt depth_limit met één verlaagd. Wanneer depth_limit 0 bereikt, schakelt het over van Quicksort naar Heapsort.

5
toegevoegd
Door je logica zal de Heapsort nooit gebeuren omdat de dieptelimiet nooit bereikt zal worden.
toegevoegd de auteur this, de bron
Lees mijn reactie hieronder; Een ander voorbeeld: Een array van 10000 leden zou een dieptelimiet van (13 * 2) hebben, als de array bij benadering bij elke recursie in tweeën wordt gedeeld, dan zullen op het 14de niveau de subarrays 0 elementen hebben.
toegevoegd de auteur this, de bron
@zelf. Waarom denk je dat?
toegevoegd de auteur Gumbo, de bron
@zelf. Welnu, in tweeën splitsen is het beste geval; in het slechtste geval wordt de reeks opgesplitst in (1, N-1). In dat geval bereikt depth_limit 0.
toegevoegd de auteur Gumbo, de bron

Ik heb net geprobeerd het inleidende Wikipedia-artikel te lezen. Het zegt

Het telt de recursiediepte. Als een logaritmische diepte wordt overschreden, de   algoritme schakelt over naar Heapsort van QuickSort om het ergste geval te behouden   uitkomst van QuickSort down

en via het originele artikel van de Musser over Introsort.

Er staat dat introsort langzamer is dan Heapsort omdat het presteert   2 * log (2, N) berekeningen voordat deze naar heapsort schakelt.

Ik heb begrepen dat de recursiediepte 2 * log (2, N) is

Om te sorteren op N = 300 elementen, is dit 2 * 8 = 16

2
toegevoegd
Als de dieptelimiet van 16 op een arry van 300 elementen op ongeveer het 10e dieptiveau wordt gebruikt, heeft de submatrix 0 elementen.
toegevoegd de auteur this, de bron