Dlaczego introsort korzysta z heapsortu, a nie z scalania?

W ramach zadania domowego obejmującego implementację introsortu jestem pytany, dlaczego stosuje się heapsort zamiast scalesort (lub inne algorytmy w tym zakresie). $O(n\log(n))$

Introsort to hybrydowy algorytm sortowania, który zapewnia zarówno szybką średnią wydajność, jak i (asymptotycznie) optymalną wydajność w najgorszym przypadku. Zaczyna się od szybkiego sortowania i przełącza się na heapsort, gdy głębokość rekurencji przekracza poziom oparty na (logarytmie) liczby sortowanych elementów. ( Wikipedia , pobrano 2014-maj-06).

Jedynym powodem, dla którego mogę wymyślić, jest to, że heapsort jest „na swoim miejscu” ... Ale tak naprawdę nie rozumiem, dlaczego miałoby to tutaj znaczenie.

algorithms algorithm-analysis sorting użytkownik672009
źródło

Jeśli introsort jest częścią pytania, musisz powiedzieć nam, co to jest, zanim będziemy mogli cokolwiek powiedzieć.

Louis

Witamy w informatyce ! Zauważ, że możesz tutaj używać LaTeXa, aby składać matematykę w bardziej czytelny sposób. Zobacz tutaj krótkie wprowadzenie.

FrankW

Jesteśmy po prostu proszeni o utworzenie pseudo kodu do sortowania wstępnego, a później pytamy, dlaczego używa on heapsortu zamiast scalania.

user672009

@ user672009 W takim przypadku zapisz kod dla jednego z nich i zobacz, co znajdziesz. Przyczyna może, ale nie musi być związana z wydajnością.

Raphael

Doszedłem do wniosku, że ponieważ szybkie sortowanie sortuje w miejscu, musimy użyć innego algorytmu sortowania w miejscu. Jestem jednak otwarty na dane wejściowe.

user672009

Odpowiedzi:

Dwie wady szybkiego sortowania polegają na tym, że wymaga ono dodatkowej przestrzeni (aby zachować nieposortowane interwały), a zły wybór osi przestawnej (lub wymyślone sekwencje mające na celu wybranie złej osi obrotu) może spowodować, że będzie to algorytm czasu i dodatkowej przestrzeni. $O(\log n)$ $O(n^2)$ $O(n)$

Przełączenie na stos rozsypisk, gdy głębokość rekurencji staje się zbyt duża (w okolicach ) oznacza, że mamy zagwarantowane górne ograniczenie, czyli czas i dodatkowe miejsce. $\log n$ $O(n \log n )$ $O( \log n)$

Wymagane dodatkowe miejsce Heapsort powoduje, że lepszym wyborem jest scalsort, w którym dla zaprojektowanej tablicy może być jeszcze duże. $O(1)$ $O(n)$ $n$

Powodem, dla którego heapsort nie jest używany do pełnego sortowania, jest to, że jest wolniejszy niż Quicksort (częściowo z powodu ukrytych stałych w dużym wyrażeniu O, a częściowo zachowania w pamięci podręcznej)

maniak zapadkowy
źródło

Ale używany jest heapsort ... i podejrzewam, że to dlatego, że jest na miejscu, jak szybki.

user672009

Podejrzewam, że @ user672009 jest zdezorientowany twoim ostatnim zdaniem. Sugeruję wyjaśnienie, że introsort nie zaczyna się od heapsortu, ponieważ jest wolniejszy.

Wandering Logic

@ user672009, przestrzeń środki „w miejscu”, a QuickSort jest nie do końca w miejscu, ponieważ wymaga dodatkowa przestrzeń.

O (1)

$O(1)$

O (\lg n)

$O(\lg n)$

Wandering Logic

Ponadto heapsort ma znacznie więcej braków pamięci podręcznej niż introsort.

noɥʇʎԀʎzɐɹƆ

Dobra implementacja Quicksort nie potrzebuje w najgorszym przypadku O (n) przestrzeni, o ile pamięta większy podinterwał na stosie i natychmiast obsługuje mniejsze.

gnasher729,