|
Strona główna
Ważniejsze 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 równy lub
większy 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 mieć 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 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 aplet 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 są zaznaczone 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 są zaznaczone białym kolorem)
Elementy porównywane są połączone szarą linią. Elementy zamieniane są zaznaczone żółtą linią.
- Aby uruchomić demonstrację, naciśnij przycisk Start.
- Aby zatrzymać demonstrację, naciśnij przycisk Stop.
- Aby wykonać jeden krok algorytmu, naciśnij przycisk Krok.
- Aby przyspieszyć demonstrację, naciśnij przycisk >.
- Aby spowolnić demonstrację, naciśnij przycisk <.
- Aby zmienić typ danych, użyj pola wyboru Typ danych.
Sortowanie stogowe
|
