|
Strona główna
Ważne definicje:
Algorytmy sortowania:
Porównanie algorytmów
Instrukcja użytkownika
Informacja o programie
|
|
Opis algorytmu
|
W tej metodzie sortowania jest wykorzystywana struktura danych zwana kopcem.
Elementy tablicy tworzą kopiec, jeżeli dla każdego indeksu i zachodzi warunek:
A[i/2] >= A[i]
Tablicę można przedstawić jako drzewo binarne, w którym kolejne jej elementy
są umieszczone poziomami od góry.
Dla tablicy o siedmiu elementach drzewo binarne ma następującą postać:
Drzewo binarne jest kopcem, jeśli każdy element jest większy lub
równy niż elementy w drzewie leżące pod nim na poziomach niższych.
Z warunku kopca (w obu sformułowaniach) wynika m.in., że w korzeniu takiego drzewa (czyli na początku tablicy)
znajduje się element maksymalny.
Bardzo ważną procedurą w algorytmie, który chcemy opisać, jest przywracanie własności kopca dla pewnego elementu A[i].
Przy wywołaniu tej procedury zakłada się, że drzewa zaczepione w lewym i prawym synu wierzchołka
zawierającego element A[i] są kopcami.
Po zakończeniu działania procedury, drzewo
zaczepione w wierzchołku zawierającym A[i] będzie spełniać własność kopca. Działanie tej procedury jest następujące:
- Jeśli element jest mniejszy od jednego ze swych synów, to zamień go z tym synem, który ma większą wartość.
- Wywołaj procedurę rekurencyjnie dla tego z synów, który zmienił wartość.
Mając tablicę, która ma własność kopca, oraz procedurę przywracania własności kopca dla zaburzonego
elementu tablicy można podać następujący algorytm porządkowania:
- Dana jest tablica
A[1..n] będąca kopcem, wobec tego element A[1] jest maksymalny.
- Niech
m oznacza ostatni element kopca; na początku kopiec obejmuje całą tablicę, więc m jest równe n.
- Zamień ze sobą elementy
A[1] i A[m].
- Zmniejsz
m o 1.
- Przywróć własność kopca dla tablicy
A[1..m] zaczynając od elementu A[1].
- Wróć do kroku 3.
Pozostaje jeszcze wyjaśnić, w jaki sposób zbudować kopiec w kroku 1. Wykorzystywana jest do tego opisana wyżej procedura
przywracania własności kopca, działająca na elementach tablicy w pewnej kolejności.
Elementy tablicy, które są liśćmi drzewa można traktować jak jednoelementowe kopce.
Procedura budująca kopiec wywołuje procedurę przywracającą własność kopca dla każdego wierzchołka,
który nie jest liściem, zaczynając od elementu leżącego najbliżej końca tablicy,
a kończąc na korzeniu drzewa.
|
Demonstracja
|
Poniższy applet demonstruje nieco dokładniej proces sortowania za pomocą kopca. Dane do sortowania mogą być losowe, uporządkowane lub odwrotnie uporządkowane.
Widok ten pokazuje dwa etapy sortowania:
- Tworzenie kopca (elementy zaznaczone są szarym kolorem). Po utworzeniu kopca algorytm zatrzymuje się. Aby kontynuować należy nacisnąć ponownie przycisk "start".
- Sortowanie z wykorzystaniem zbudowanego kopca (elementy będące w kopcu zaznaczone są białym kolorem)
Elementy porównywane połączone są szarą linią. Elementy zamieniane zaznaczone są żółtą linią.
- Aby uruchomić demonstrację naciśnij Start.
- Aby zatrzymać demonstrację naciśnij Stop.
- Aby wykonać jeden krok algorytmu naciśnij Krok.
- Aby przyspieszyć działanie naciśnij >.
- Aby spowolnić działanie naciśnij <.
- Aby zmienić typ danych użyj pola wyboru poniżej.
- Aby zmienić wielkość danych użyj pola edycyjnego i przycisku Zmień.
Sortowanie stogowe
|
