|
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 opisany algorytm sortowania. Dane do sortowania mogą być losowe, uporządkowane lub odwrotnie uporządkowane.
Dostępna jest również nieco inna demonstracja tego samego algorytmu, z danymi w postaci drzewa.
- Zieloną i niebieską kropką są zaznaczone aktualnie porównywane elementy.
- Żółtą linią jest oznaczona uporządkowana część ciągu.
- 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ń.
Wielkość danych musi być liczbą z zakresu od 5 do 300.
|
