Pytanie w sprawie introsort, sorting, algorithm – Kiedy introsort zmienia się z quicksort na heapsort?

6

Introsort zaczyna się od quicksort i przełącza na heapsort, gdy głębokość rekurencji przekracza poziom oparty na liczbie sortowanych elementów. Co to za numer? Czy istnieje określony zakres lub wartość graniczna?

Twoja odpowiedź

2   odpowiedź
6

Algorytm introsortowy przełączenia z Quicksort na Heapsort są określane przezdeep_limit:

deep_limit = 2 · ⎣log2(l) ⎦

Gdziel to długość sekwencji, która ma zostać posortowanal‍ = ‍n dla całej sekwencji. Z każdym wywołaniem rekurencyjnymdeep_limit jest zmniejszany o jeden. Gdydeep_limit osiąga 0, przełącza się z Quicksort na Heapsort.

@samego siebie. Dlaczego tak myślisz? Gumbo
@samego siebie. Cóż, podział na pół jest najlepszym przypadkiem; w najgorszym przypadku sekwencja zostanie podzielona na (1, N-1). W takim przypadku limit_głębienia osiągnie 0. Gumbo
Przeczytaj mój komentarz poniżej; inny przykład: Tablica 10000 członków miałaby limit głębokości (13 * 2), jeśli tablica jest w przybliżeniu podzielona na połowę przy każdej rekurencji, to na 14 poziomie macierze będą miały 0 elementów. this
Zgodnie z twoją logiką Heapsort nigdy się nie stanie, ponieważ limit głębokości nigdy nie zostanie osiągnięty. this
2

Artykuł w Wikipedii. To mówi

Zlicza głębokość rekurencji. Jeśli przekroczona zostanie logarytmiczna głębokość, algorytm przełącza się na Heapsort z Quicksort, aby zachować najgorszy wynik Quicksort down

i poprzez oryginalny dokument Musser'a na temat Introsortu.

Mówi, że introsort jest wolniejszy niż heapsort, ponieważ wykonuje 2 * log (2, N) obliczeń, zanim przełączy się na heapsort.

Rozumiem, że głębokość rekurencji wynosi 2 * log (2, N)

Dla N = 300 elementów do sortowania będzie to 2 * 8 = 16

Jeśli użyjesz limitu głębokości 16 na arii 300 elementów na poziomie około 10 głębokości, to podarray będzie miał 0 elementów. this

Powiązane pytania