Sortowanie — Heapsort

Heapsort

Przebieg sortowania sterty sortujący tablicę losowo permutowanych wartości. W pierwszym etapie algorytmu elementy tablicy są uporządkowane tak, aby spełniały właściwość sterty . Przed faktycznym sortowaniem przedstawiono pokrótce strukturę drzewa sterty dla ilustracji.
Klasa	Algorytm sortowania
Struktura danych	Szyk
Wydajność w najgorszym przypadku	${\ Displaystyle O (n \ log n)}$
Wydajność w najlepszym przypadku	${\ Displaystyle O (n \ log n)}$(różne klawisze) lub (równe klawisze)${\ Displaystyle O (n)}$
Średnia wydajność	${\ Displaystyle O (n \ log n)}$
Najgorsza złożoność przestrzeni	${\ Displaystyle O (n)}$całkowity pomocniczy${\ Displaystyle O (1)}$

W informatyce , sortowanie przez kopcowanie jest porównanie oparte algorytm sortowania . Heapsort można traktować jako ulepszone sortowanie przez wybór : podobnie jak sortowanie przez wybór, sortowanie przez wybór dzieli swoje dane wejściowe na posortowany i nieposortowany region i iteracyjnie zmniejsza nieposortowany region, wyodrębniając z niego największy element i wstawiając go do posortowanego regionu. W przeciwieństwie do sortowania przez wybór, sortowanie na stercie nie marnuje czasu na skanowanie w czasie liniowym nieposortowanego regionu; sortowanie sterty utrzymuje niesortowany region w strukturze danych sterty , aby szybciej znaleźć największy element w każdym kroku.

Chociaż w praktyce jest nieco wolniejszy na większości komputerów niż dobrze zaimplementowany quicksort , ma on tę zaletę, że jest korzystniejszy w najgorszym przypadku środowiska uruchomieniowego O( n log n ) . Heapsort to algorytm w miejscu , ale nie jest to sortowanie stabilne .

Heapsort został wynaleziony przez JWJ Williamsa w 1964 roku. Były to również narodziny stosu, przedstawionego już przez Williamsa jako użyteczna struktura danych sama w sobie. W tym samym roku RW Floyd opublikował ulepszoną wersję, która może sortować tablicę w miejscu, kontynuując swoje wcześniejsze badania nad algorytmem sortowania drzew .

Przegląd

Algorytm sortowania sterty można podzielić na dwie części.

W pierwszym kroku z danych budowana jest sterta (patrz Sterta binarna § Budowanie sterty ). Sterta jest często umieszczana w tablicy z układem pełnego drzewa binarnego . Kompletne drzewo binarne odwzorowuje strukturę drzewa binarnego na indeksy tablicy; każdy indeks tablicy reprezentuje węzeł; indeks rodzica węzła, lewa gałąź podrzędna lub prawa gałąź podrzędna są prostymi wyrażeniami. W przypadku tablicy liczonej od zera węzeł główny jest przechowywany pod indeksem 0; jeśli ijest indeksem bieżącego węzła, to

  iParent(i)     = floor((i-1) / 2) where floor functions map a real number to the smallest leading integer.
  iLeftChild(i)  = 2*i + 1
  iRightChild(i) = 2*i + 2

W drugim kroku posortowana tablica jest tworzona przez wielokrotne usuwanie największego elementu ze sterty (korzeń sterty) i wstawianie go do tablicy. Sterta jest aktualizowana po każdym usunięciu, aby zachować właściwość sterty. Po usunięciu wszystkich obiektów ze sterty wynikiem jest posortowana tablica.

Heapsort można przeprowadzić na miejscu. Tablicę można podzielić na dwie części, posortowaną tablicę i stertę. Przechowywanie stert w postaci tablic jest tutaj przedstawione w formie diagramu . Niezmiennik hałdy jest zachowywany po każdym wydobyciu, więc jedynym kosztem jest wydobycie.

Algorytm

Algorytm Heapsort polega na przygotowaniu listy, najpierw przekształcając ją w max stertę . Algorytm następnie wielokrotnie zamienia pierwszą wartość listy z ostatnią wartością, zmniejszając zakres wartości rozważanych w operacji sterty o jeden i przesiewając nową pierwszą wartość na jej pozycję w stercie. Powtarza się to, dopóki zakres rozważanych wartości nie będzie miał jednej wartości długości.

Kroki to:

1. Wywołaj funkcję buildMaxHeap() z listy. Nazywany również heapify(), buduje stertę z listy w operacjach O(n).
2. Zamień pierwszy element listy na ostatni element. Zmniejsz rozważany zakres listy o jeden.
3. Wywołaj funkcję siftDown() na liście, aby przesiać nowy pierwszy element do odpowiedniego indeksu w stercie.
4. Przejdź do kroku (2), chyba że rozważany zakres listy jest jednym elementem.

Operacja buildMaxHeap() jest uruchamiana raz i ma wydajność O( n ) . Funkcja siftDown() to O(log n ) i jest wywoływana n razy. Dlatego wydajność tego algorytmu wynosi O( n + n log n ) = O( n log n ) .

Pseudo kod

Poniżej przedstawiono prosty sposób zaimplementowania algorytmu w pseudokodzie . Tablice są liczone od zera i swapsłużą do wymiany dwóch elementów tablicy. Ruch „w dół” oznacza od nasady w kierunku liści lub od niższych indeksów do wyższych. Zauważ, że podczas sortowania największy element znajduje się w korzeniu sterty w a[0], podczas gdy na końcu sortowania największy element znajduje się w a[end].

procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (the heap size is reduced by one)
        end ← end - 1
        (the swap ruined the heap property, so restore it)
        siftDown(a, 0, end)

Procedura sortowania używa dwóch podprogramów heapifyi siftDown. Pierwsza jest powszechną procedurą budowy sterty w miejscu, podczas gdy druga jest powszechną procedurą do implementacji heapify.

(Put elements of 'a' in heap order, in-place)
procedure heapify(a, count) is
    (start is assigned the index in 'a' of the last parent node)
    (the last element in a 0-based array is at index count-1; find the parent of that element)
    start ← iParent(count-1)
    
    while start ≥ 0 do
        (sift down the node at index 'start' to the proper place such that all nodes below
         the start index are in heap order)
        siftDown(a, start, count - 1)
        (go to the next parent node)
        start ← start - 1
    (after sifting down the root all nodes/elements are in heap order)

(Repair the heap whose root element is at index 'start', assuming the heaps rooted at its children are valid)
procedure siftDown(a, start, end) is
    root ← start

    while iLeftChild(root) ≤ end do    (While the root has at least one child)
        child ← iLeftChild(root)   (Left child of root)
        swap ← root                (Keeps track of child to swap with)

        if a[swap] < a[child] then
            swap ← child
        (If there is a right child and that child is greater)
        if child+1 ≤ end and a[swap] < a[child+1] then
            swap ← child + 1
        if swap = root then
            (The root holds the largest element. Since we assume the heaps rooted at the
             children are valid, this means that we are done.)
            return
        else
            swap(a[root], a[swap])
            root ← swap            (repeat to continue sifting down the child now)

heapifyProcedura może być traktowane jako budowanie sterty oddolnie przez odsiewanie kolejno w dół w celu ustalenia własności sterty . Alternatywna wersja (pokazana poniżej), która buduje stertę od góry do dołu i przesuwa się w górę, może być łatwiejsza do zrozumienia. siftUpWersję tę można zwizualizować jako rozpoczynającą się od pustej sterty i sukcesywnie wstawiającej elementy, podczas gdy siftDownwersja podana powyżej traktuje całą tablicę wejściową jako pełną, ale „zepsutą” stertę i „naprawia” ją, zaczynając od ostatniego nietrywialnego podzwału ( czyli ostatni węzeł nadrzędny).

Różnica w złożoności czasowej między wersją „siftDown” a wersją „siftUp”.

Również siftDownwersja heapify ma złożoność czasową O ( n ) , podczas gdy siftUpwersja podana poniżej ma złożoność czasową O ( n log n ) ze względu na jej równoważność z wstawianiem każdego elementu, po jednym na raz, do pustej sterty. Może się to wydawać sprzeczne z intuicją, ponieważ na pierwszy rzut oka widać, że pierwsza z nich wykonuje tylko o połowę mniej wywołań swojej funkcji przesiewania logarytmicznego w czasie niż druga; tzn. wydają się różnić tylko stałym czynnikiem, który nigdy nie wpływa na analizę asymptotyczną.

Aby zrozumieć intuicję stojącą za tą różnicą w złożoności, zauważ, że liczba zamian, które mogą wystąpić podczas jednego wywołania siftUp, wzrasta wraz z głębokością węzła, na którym wykonywane jest wywołanie. Sedno polega na tym, że istnieje wiele (wykładniczo wiele) więcej „głębokich” węzłów niż „płytkich” węzłów w stercie, tak że siftUp może mieć swój pełny logarytmiczny czas działania na w przybliżeniu liniowej liczbie wywołań wykonanych na węzłach w lub w pobliżu „dna” sterty. Z drugiej strony, liczba zamian, które mogą wystąpić podczas jednego wywołania siftDown, zmniejsza się wraz ze wzrostem głębokości węzła, na którym wykonywane jest wywołanie. Tak więc, gdy siftDown heapifyrozpoczyna się i wywołuje siftDownna najniższej i najliczniejszej warstwie węzłów, każde wywołanie przesiewania spowoduje co najwyżej liczbę zamian równą „wysokości” (od dołu sterty) węzła, na którym następuje przesiewanie. Innymi słowy, około połowa połączeń do siftDown będzie miała najwyżej jedną zamianę, następnie około jedna czwarta połączeń będzie miała najwyżej dwie zamiany itd.

Sam algorytm sortowania sterty ma złożoność czasową O ( n log n ) przy użyciu dowolnej wersji heapify.

 procedure heapify(a,count) is
     (end is assigned the index of the first (left) child of the root)
     end := 1
     
     while end < count
         (sift up the node at index end to the proper place such that all nodes above
          the end index are in heap order)
         siftUp(a, 0, end)
         end := end + 1
     (after sifting up the last node all nodes are in heap order)
 
 procedure siftUp(a, start, end) is
     input:  start represents the limit of how far up the heap to sift.
                   end is the node to sift up.
     child := end 
     while child > start
         parent := iParent(child)
         if a[parent] < a[child] then (out of max-heap order)
             swap(a[parent], a[child])
             child := parent (repeat to continue sifting up the parent now)
         else
             return

Zauważ, że w przeciwieństwie do siftDownpodejścia, w którym po każdej wymianie musisz wywołać tylko siftDownpodprogram, aby naprawić zepsutą stertę; siftUpsam podprogram nie może naprawić uszkodzony sterty. Sterta musi być budowana za każdym razem po zamianie przez wywołanie heapifyprocedury, ponieważ "siftUp" zakłada, że ​​element, który jest wymieniany, kończy się na swoim ostatecznym miejscu, w przeciwieństwie do "siftDown" pozwala na ciągłe dostosowywanie elementów znajdujących się niżej w stercie, aż do niezmiennik jest spełniony. Dopasowany pseudokod do użycia siftUppodejścia podano poniżej.

 procedure heapsort(a, count) is
    input: an unordered array a of length count
 
    (Build the heap in array a so that largest value is at the root)
    heapify(a, count)

    (The following loop maintains the invariants that a[0:end] is a heap and every element
     beyond end is greater than everything before it (so a[end:count] is in sorted order))
    end ← count - 1
    while end > 0 do
        (a[0] is the root and largest value. The swap moves it in front of the sorted elements.)
        swap(a[end], a[0])
        (rebuild the heap using siftUp after the swap ruins the heap property)
        heapify(a, end)
        (reduce the heap size by one)
        end ← end - 1

Wariacje

Budowa sterty Floyda

Najważniejszą odmianą podstawowego algorytmu, która jest zawarta we wszystkich praktycznych implementacjach, jest algorytm budowy sterty autorstwa Floyda, który działa w czasie O ( n ) i używa siftdown zamiast siftup , unikając w ogóle potrzeby implementacji siftup.

Zamiast zaczynać od trywialnej sterty i wielokrotnie dodawać liście, algorytm Floyda zaczyna od liści, obserwując, że są one trywialnymi, ale prawidłowymi stertami same z siebie, a następnie dodaje rodziców. Zaczynając od elementu n /2 i pracując wstecz, każdy węzeł wewnętrzny staje się korzeniem prawidłowego sterty przez przesiewanie w dół. Ostatnim krokiem jest przesiewanie pierwszego elementu, po czym cała tablica przestrzega właściwości sterty.

Wiadomo, że najgorsza liczba porównań podczas fazy budowy sterty Floyda w Heapsort wynosi 2 n - 2 s ₂ ( n ) - e ₂ ( n ) , gdzie s ₂ ( n ) jest liczbą 1 bitów w binarnej reprezentacji n i e ₂ ( n ) jest liczbą końcowych bitów 0.

Standardowa implementacja algorytmu budowy sterty Floyda powoduje dużą liczbę chybień w pamięci podręcznej, gdy rozmiar danych przekracza rozmiar pamięci podręcznej procesora . Znacznie lepszą wydajność na dużych zestawach danych można uzyskać, scalając w pierwszej kolejności głębię , łącząc podzsypy tak szybko, jak to możliwe, zamiast łączenia wszystkich podstert na jednym poziomie przed przejściem do powyższego.

Oddolne sortowanie

Sortowanie od dołu do góry to wariant, który znacznie zmniejsza liczbę porównań wymaganych przez istotny czynnik. Podczas gdy zwykłe sortowanie wymaga 2 n log ₂ n + O ( n ) porównań w najgorszym przypadku i średnio, wariant oddolny wymaga średnio n log ₂ n + O (1) porównań i 1,5 n log ₂ n + O ( n ) w najgorszym przypadku.

Jeśli porównania są tanie (np. klucze całkowite), to różnica jest nieistotna, ponieważ sortowanie odgórne porównuje wartości, które zostały już załadowane z pamięci. Jeśli jednak porównania wymagają wywołania funkcji lub innej złożonej logiki, korzystne jest sortowanie od dołu do góry.

Osiąga się to poprzez ulepszenie siftDownprocedury. Zmiana nieco poprawia fazę budowania stosu w czasie liniowym, ale jest bardziej znacząca w drugiej fazie. Podobnie jak w przypadku zwykłego sortowania, każda iteracja drugiej fazy wyodrębnia wierzchołek sterty, a [0] i wypełnia lukę, którą pozostawia, za pomocą [ end ] , a następnie przesiewa ten ostatni element w dół sterty. Ale ten element pochodzi z najniższego poziomu sterty, co oznacza, że ​​jest jednym z najmniejszych elementów w stercie, więc przesiewanie prawdopodobnie wykona wiele kroków, aby przesunąć go z powrotem w dół. W zwykłym sortowaniu na stercie każdy krok przesiewania wymaga dwóch porównań, aby znaleźć co najmniej trzy elementy: nowy węzeł i jego dwoje dzieci.

Zamiast tego sortowanie od dołu do góry znajduje ścieżkę największych dzieci do poziomu liścia drzewa (tak jakby wstawiało −∞) używając tylko jednego porównania na poziom. Innymi słowy, znajduje liść, który ma tę właściwość, że on i wszyscy jego przodkowie są więksi lub równi swojemu rodzeństwu. (W przypadku braku równych klucze, to skrzydło jest unikalny). Następnie, na liściach, przeszukuje góry (za pomocą jednego bezpośredniego porównania poziomu) do odpowiedniej pozycji na ścieżce, aby wstawić w [ koniec ] . Jest to ta sama lokalizacja, co zwykłe znaleziska sortowania sterty i wymaga takiej samej liczby wymian do wykonania wstawiania, ale do znalezienia tej lokalizacji wymagana jest mniejsza liczba porównań.

Ponieważ schodzi na sam dół, a potem wraca do góry, niektórzy autorzy nazywają go sortowaniem sterty z odbiciem .

function leafSearch(a, i, end) is
    j ← i
    while iRightChild(j) ≤ end do
        (Determine which of j's two children is the greater)
        if a[iRightChild(j)] > a[iLeftChild(j)] then
            j ← iRightChild(j)
        else
            j ← iLeftChild(j)
    (At the last level, there might be only one child)
    if iLeftChild(j) ≤ end then
        j ← iLeftChild(j)
    return j

Zwracana wartość the leafSearchjest używana w zmodyfikowanej siftDownprocedurze:

procedure siftDown(a, i, end) is
    j ← leafSearch(a, i, end)
    while a[i] > a[j] do
        j ← iParent(j)
    x ← a[j]
    a[j] ← a[i]
    while j > i do
        swap x, a[iParent(j)]
        j ← iParent(j)

Sortowanie od dołu do góry zostało ogłoszone jako szybkie sortowanie (z wyborem mediany z trzech przestawnych) na tablicach o rozmiarze ≥16000.

Ponowna ocena tego algorytmu w 2008 r. wykazała, że ​​nie jest on szybszy niż zwykłe sortowanie sterty dla kluczy całkowitych, prawdopodobnie dlatego, że współczesne przewidywanie rozgałęzień unieważnia koszt przewidywalnych porównań, których udaje się uniknąć oddolnego sortowania sterty.

Dalsze udoskonalenie polega na przeszukiwaniu binarnym ścieżki do wybranego liścia i sortowaniu w najgorszym przypadku ( n +1)(log ₂ ( n +1) + log ₂ log ₂ ( n +1) + 1,82) + O (log ₂ n ) porównań, zbliżając się z informacjami, teoretycznie dolna granica z n log ₂ n - 1.4427 n porównań.

Wariant, który wykorzystuje dwa dodatkowe bity na węzeł wewnętrzny ( łącznie n -1 bitów na stertę n- elementową) do buforowania informacji o tym, który potomek jest większy (dwa bity są wymagane do przechowania trzech przypadków: lewego, prawego i nieznanego) używa less niż n log ₂ n + 1,1 n porównań.

Inne odmiany

• Sortowanie stosu trójargumentowego używa sterty trójargumentowej zamiast sterty binarnej; oznacza to, że każdy element w stercie ma troje dzieci. Programowanie jest bardziej skomplikowane, ale wykonuje stałą liczbę razy mniej operacji wymiany i porównania. Dzieje się tak, ponieważ każdy krok przesiewania w stercie trójskładnikowej wymaga trzech porównań i jednej zamiany, podczas gdy w stercie binarnej wymagane są dwa porównania i jedna zamiana. Dwa poziomy w stercie trójskładnikowej pokrywają 3 ² = 9 elementów, wykonując więcej pracy z taką samą liczbą porównań, jak trzy poziomy w stercie binarnej, które pokrywają tylko 2 ³ = 8. Jest to głównie interesujące akademickie lub jako ćwiczenie dla uczniów , ponieważ dodatkowa złożoność nie jest warta drobnych oszczędności, a sortowanie od dołu do góry bije jedno i drugie.
• Heapsort zoptymalizowany pod kątem pamięci poprawia lokalizację odniesienia Heapsort, jeszcze bardziej zwiększając liczbę dzieci. Zwiększa to liczbę porównań, ale ponieważ wszystkie elementy podrzędne są przechowywane kolejno w pamięci, zmniejsza liczbę linii pamięci podręcznej, do których uzyskuje się dostęp podczas przechodzenia sterty, co stanowi poprawę wydajności sieci.
• Sortowanie sterty poza miejscem poprawia sortowanie od dołu do góry, eliminując najgorszy przypadek, gwarantując n log ₂ n + O ( n ) porównań. Kiedy zostanie zrobione maksimum, zamiast wypełniać puste miejsce nieposortowaną wartością danych, wypełnij ją wartością wskaźnika -∞ , która nigdy nie "odbija się" z powrotem. Okazuje się, że można to wykorzystać jako prymityw w lokalnym (i nierekurencyjnym) algorytmie „QuickHeapsort”. Najpierw wykonujesz przebieg partycjonowania podobny do szybkiego sortowania, ale odwracając kolejność partycjonowanych danych w tablicy. Załóżmy ( bez utraty ogólności ), że mniejsza partycja to ta większa niż element obrotowy, który powinien znajdować się na końcu tablicy, ale nasz krok odwróconego partycjonowania umieszcza ją na początku. Uformuj stertę z mniejszej partycji i wykonaj na niej sortowanie poza miejscem, wymieniając wyodrębnione maksima z wartościami z końca tablicy. Są to wartości mniejsze niż piwot, co oznacza mniej niż jakakolwiek wartość w stercie, więc służą jako wartości -∞ wartości wskaźnikowych . Po zakończeniu sortowania sterty (i przestawieniu elementu obrotowego tuż przed posortowanym końcem tablicy) kolejność partycji została odwrócona, a większą partycję na początku tablicy można posortować w ten sam sposób. (Ponieważ nie ma rekurencji bez ogona , eliminuje to również użycie stosu O (log n ) w quicksort ) .
• Smoothsort algorytm jest odmianą sortowanie przez kopcowanie opracowany przez Edsger Dijkstra w 1981 Ci się sortowanie przez kopcowanie, smoothsort to górna granica jest O ( n log n ) . Zaletą smoothsort jest to, że zbliża się do czasu O ( n ) , jeśli dane wejściowe są już w pewnym stopniu posortowane , podczas gdy sortowanie przez stertę uśrednia O ( n log n ) niezależnie od początkowego stanu sortowania. Ze względu na swoją złożoność, smoothsort jest rzadko używany.
• Levcopoulos i Petersson opisują odmianę sortowania sterty opartą na stercie drzew kartezjańskich . Najpierw z danych wejściowych w czasie O ( n ) budowane jest drzewo kartezjańskie , a jego korzeń jest umieszczany w 1-elementowym stercie binarnym. Następnie wielokrotnie wyodrębniamy minimum ze sterty binarnej, wyprowadzamy element główny drzewa i dodajemy jego lewy i prawy dzieci (jeśli istnieją), które same są drzewami kartezjańskimi, do sterty binarnej. Jak pokazują, jeśli dane wejściowe są już prawie posortowane, drzewa kartezjańskie będą bardzo niezrównoważone, z kilkoma węzłami mającymi lewe i prawe dzieci, co spowoduje, że stos binarny pozostanie mały i pozwoli algorytmowi sortować szybciej niż O ( n log n ) dla danych wejściowych, które są już prawie posortowane.
• Kilka wariantów, takich jak słabe sortowanie sterty, wymaga porównań n log ₂ n + O (1) w najgorszym przypadku, zbliżonym do teoretycznego minimum, przy użyciu jednego dodatkowego bitu stanu na węzeł. Chociaż ten dodatkowy bit sprawia, że ​​algorytmy nie są tak naprawdę na miejscu, jeśli można znaleźć dla niego miejsce w elemencie, algorytmy te są proste i wydajne, ale wciąż wolniejsze niż stosy binarne, jeśli porównania kluczy są wystarczająco tanie (np. klucze całkowite), aby stały czynnik nie ma znaczenia.
• „Ostateczne sortowanie” Katajainena nie wymaga dodatkowej pamięci, wykonuje n log ₂ n + O (1) porównań i podobną liczbę ruchów elementów. Jest to jednak jeszcze bardziej złożone i nieuzasadnione, chyba że porównania są bardzo drogie.

Porównanie z innymi rodzajami

Heapsort konkuruje przede wszystkim z quicksort , innym bardzo wydajnym algorytmem sortowania ogólnego przeznaczenia opartym na porównaniu.

Podstawowymi zaletami Heapsort są jego prosty, nierekurencyjny kod, minimalne wymagania dotyczące pamięci pomocniczej i niezawodnie dobra wydajność: najlepsze i najgorsze przypadki mieszczą się w małym stałym współczynniku między sobą oraz teoretycznej dolnej granicy sortowania porównawczego . Chociaż nie może zrobić lepiej niż O ( n log n ) dla wstępnie posortowanych danych wejściowych, nie ma też najgorszego przypadku quicksort O ( n ² ) . (Tego ostatniego można uniknąć dzięki starannej implementacji, ale to sprawia, że ​​sortowanie quicksort jest znacznie bardziej złożone, a jedno z najpopularniejszych rozwiązań, introsort , używa do tego celu sortowania stertowego ).

Jego główne wady to słaba lokalizacja odniesienia i z natury seryjny charakter; dostępy do niejawnego drzewa są szeroko rozproszone i przeważnie losowe, i nie ma prostego sposobu na przekształcenie go w algorytm równoległy .

To sprawia, że ​​jest popularny w systemach wbudowanych , przetwarzaniu w czasie rzeczywistym i systemach związanych ze złośliwie wybranymi danymi wejściowymi, takimi jak jądro Linux. Jest to również dobry wybór dla każdej aplikacji, która nie przewiduje wąskich gardeł podczas sortowania.

Dobrze zaimplementowane sortowanie szybkie jest zwykle 2-3 razy szybsze niż sortowanie sterty. Chociaż szybkie sortowanie wymaga mniejszej liczby porównań, jest to niewielki czynnik. (Wyniki twierdzące, że dwa razy więcej porównań mierzą wersję od góry do dołu; patrz § Sortowanie sterty od dołu do góry .) Główną zaletą szybkiego sortowania jest znacznie lepsza lokalizacja odniesienia: partycjonowanie jest skanowaniem liniowym z dobrą lokalizacją przestrzenną i rekurencyjnym podziałem ma dobrą lokalizację czasową. Z dodatkowym wysiłkiem quicksort można również zaimplementować w większości kodu bez gałęzi , a do równoległego sortowania podpartycji można użyć wielu procesorów. Dlatego sortowanie szybkie jest preferowane, gdy dodatkowa wydajność uzasadnia wysiłek związany z implementacją.

Innym głównym algorytmem sortowania O ( n log n ) jest sortowanie przez scalanie , ale rzadko konkuruje on bezpośrednio z sortowaniem sterty, ponieważ nie jest na miejscu. Wymóg sortowania przez scalanie dotyczący dodatkowej przestrzeni Ω( n ) (mniej więcej połowa rozmiaru danych wejściowych) jest zwykle niedopuszczalny, z wyjątkiem sytuacji, w których sortowanie przez scalanie ma wyraźną przewagę:

• Kiedy wymagane jest stabilne sortowanie
• Korzystając z (częściowo) wstępnie posortowanych danych wejściowych
• Sortowanie list połączonych (w takim przypadku sortowanie przez scalanie wymaga minimalnej dodatkowej przestrzeni)
• Sortowanie równoległe; sortowanie przez scalanie przebiega równolegle nawet lepiej niż sortowanie szybkie i może z łatwością osiągnąć przyspieszenie zbliżone do liniowego
• Sortowanie zewnętrzne ; sortowanie przez scalanie ma doskonałą lokalizację odniesienia

Przykład

Niech { 6, 5, 3, 1, 8, 7, 2, 4 } będzie listą, którą chcemy posortować od najmniejszej do największej. (UWAGA, dla kroku „Budowanie sterty”: Większe węzły nie pozostają poniżej mniejszych rodziców węzłów. Są one zamieniane z rodzicami, a następnie rekurencyjnie sprawdzane, czy potrzebna jest kolejna zamiana, aby utrzymać większe liczby powyżej mniejszych liczb w drzewie binarnym sterty .)

Przykład na sortowaniu.

Uwagi

Bibliografia

• Williams, JWJ (1964), "Algorytm 232 - Heapsort", Komunikacja ACM , 7 (6): 347-348, doi : 10.1145/512274.512284
• Floyd, Robert W. (1964), "Algorytm 245 - Treesort 3", Komunikacja ACM , 7 (12): 701, doi : 10.1145/355588.365103 , S2CID  52864987
• Carlsson, Svante (1987), "Średnia-przypadek wyniki na Heapsort", BIT , 27 (1): 2-17, doi : 10.1007/bf01937350 , S2CID  31450060
• Knuth, Donald (1997), „§ 5.2.3, Sortowanie według selekcji”, Sortowanie i wyszukiwanie , The Art of Computer Programming , 3 (wyd. trzecie), Addison-Wesley, s. 144-155, ISBN 978-0-201-89685-5
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest i Clifford Stein . Wprowadzenie do algorytmów , wydanie drugie. MIT Press i McGraw-Hill, 2001. ISBN  0-262-03293-7 . Rozdziały 6 i 7 odpowiednio: Heapsort i kolejki priorytetowe
• PDF z oryginalnym artykułem Dijkstry na Smoothsort
• Heaps and Heapsort Tutorial autorstwa Davida Carlsona, St. Vincent College

Linki zewnętrzne

• Animowane algorytmy sortowania: Heap Sort at the Wayback Machine (archiwum 6 marca 2015) – demonstracja graficzna
• Materiały szkoleniowe na Heapsort z Univ. Oldenburg - Z tekstem, animacjami i ćwiczeniami interaktywnymi
• Słownik algorytmów i struktur danych NIST: Heapsort
• Heapsort zaimplementowany w 12 językach
• Sortowanie ponownie odwiedzone przez Paula Hsieh
• Prezentacja programu PowerPoint pokazująca, jak działa sortowanie sterty, która jest przeznaczona dla nauczycieli.
• Otwarte struktury danych - Sekcja 11.1.3 - Sortowanie na stercie , Pat Morin