algorytm.org

Sortowanie stogowe (heapsort)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie stogowe (heapsort)
Ocena użytkowników:***** / 34
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 13 sierpnia 2005 10:47

Jest to metoda bardziej skomplikowana niż sortowanie bąbelkowe czy przez wstawianie, ale za to działa w krótszym czasie. Zrozumienie algorytmu HeapSort wymaga zaznajomienia się z pojęciem Kopca/Stogu. Budowa drzewa binarnego z elementów tablicy, którą mamy posortować wygląda następująco:
  • Zaczynamy od pierwszego elementu tablicy, który będzie korzeniem
  • Każdy następny i-ty element tablicy będzie miał co najwyżej dwa następniki o wyrazach odpowiednio: 2*i oraz 2*i+1
  • Łatwo stwierdzić, że dla każdego i-tego elementu (oprócz korzenia) numer elementu w tablicy, będącego jego poprzednikiem określa się wzorem: i div 2

Po zbudowaniu drzewa należy wykonać odpowiednie instrukcje, które zapewnią mu warunek kopca. Należy więc sprawdzać (poczynając od poprzednika ostatniego liścia schodząc w górę do korzenia) czy poprzednik jest mniejszy od następnika i jeżeli tak jest to zamienić je miejscami. Po wykonaniu tych czynności drzewo binarne zamieniło się w stóg. Z jego własności wynika, że w korzeniu znajduje się największy element. Korzystając z tego faktu możemy go pobrać na koniec tablicy wynikowej a na jego miejsce wstawić ostatni liść. Po pobraniu korzenia tablica źródłowa zmniejszyła się o 1 element a porządek kopca został zaburzony (nie wiadomo, czy ostatni liść będący teraz korzeniem jest rzeczywiście największym elementem). By przywrócić warunek stogu należy ponownie uporządkować jego elementy, tym razem jednak zaczynając od korzenia (ponieważ to on jest nowym elementem). Po przywróceniu porządku w kopcu możemy znów pobrać korzeń i wstawić go do tablicy wynikowej (tym razem na drugie miejsce od końca), wstawić na jego miejsce liść i zmniejszyć rozmiar tablicy źródłowej o 1. Tu pętla się zamyka. Wykonujemy te czynności aż do ostatniego korzenia. Po całkowitym wyczyszczeniu kopca w tablicy wynikowej będziemy mieli posortowane elementy z tablicy wejściowej. Aby zlikwidować drugą tablicę (co zwiększa złożoność pamięciową algorytmy) wystarczy w kolejnych krokach odkładać korzenie w tej samej tablicy, od końca zmniejszając jednocześnie zmienną, która odpowiada za liczbę elementów kopca. Po zmniejszeniu tej liczby algorytm nie będzie "widział" tylnej, posortowanej już części tablicy.
Złożoność tego algorytmu to O(nlogn).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
MarianC/C++
.cpp
.cpp
***** / 10
MarianC/C++C++
.cpp
.cpp
***** / 18
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 5
Marek RynarzewskiPhp
.php
.php
***** / 2
Rafał GawlikPythonPython2, Python3
.py
.py
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 26 lipca 2012 15:02
Komentarze
photo
+15 # anonymous 2010-01-19 14:27
"schodząc w górę do korzenia" brzmi zaje*iście ;p
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Max 2010-07-31 14:59
Prosił bym jakąś kompetentną osobę o zamieszczenie kodu tego algorytmu w języku C++ będe wdzięczny (i podejrzewam że nietylko ja)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # AdamMTT 2012-02-03 07:45
Ja z kolei proszę o implementacje kodu w c#
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # kpalka 2013-01-30 23:00
Może przyda się osobą piszącym algorytm w językach w których numerowanie tablic zaczyna się od 0 (chyba w większości). Indeks rodzica to (n-1)/2; lewego dziecka 2n+1; prawego dziecka 2n+2. Podane w artykule wartości działają w tablicach numerowanych od 1 (jak w przykładach implementacji w Cormenie) i jak niektórzy żywcem przepisują do języków podobnych do C, to jako lewe dziecko np. dla korzenia mają korzenia :) (lChild = 0*2).
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz