1800320378

uporządkowanego kopcowo, którego węzeł na pozycji k jest większy, lub równy węzłom na pozycjach 3k-I, 3k, 3k+ 1, jest mniejszy lub równy niż węzeł na pozycji E((k+J)/3) dla pozycji z przedziału od 1 do n w tablicy n-elementowej. Mniejszy koszt wypływający z faktu zredukowanej wysokości drzewa, pociąga ze sobą wyższy koszt sprawdzania 3 węzłów potomnych, w każdym rozpatrywanym węźle. Dalsze zwiększanie liczby potomków przypadających na jeden węzeł nie powoduje raczej zwiększenia ogólnej wydajności algorytmu.

4. Wnioski

Sortowanie stogowejest bardzo specyficznym rodzajem sortowania. Z pewnością nie nadaje się do sortowania małych zbiorów danych, ponieważ lepiej wtedy użyć algorytmu QuickSort, który jest szybszy. Wymaga zastosowania określonej struktury danych, co ogranicza jego stosowanie i komplikuje implementację. Niestety, jest również algorytmem niestabilnym co może, w niektórych wypadkach powodować niemożność posortowania danych(w takim przypadku wybiera się inny). Problemem jest również to, iż działając na strukturze statycznej (np. tablicy) pojawia się ograniczenie ilości danych. HeapSort na strukturze dynamicznej jest bardzo trudny do zaimplementowania, choć jego złożoność obliczeniowa jest mniej więcej taka sama (niestety w takiej strukturze złożoność pamięciowa nie jest już stała).

HeapSort najlepiej sprawdza się w sortowaniu dużych zbiorów danych, ułożenie danych w strukturę kopca, powoduje zmniejszenie złożoności obliczeniowej wykonywanych operacji do rzędu 0(log n) co daje dużą szybkość. Jest również algorytmem bardzo nie wrażliwym na uporządkowanie danych, co czyni go czasem szybszym niż QuickSort. Sortując w miejscu zapewnia sobie złożoność pamięciową rzędu 0(1) co jest najlepszym wyborem. Bardzo ważne również jest to, iż w każdym, a nawet najgorszym wypadku jego złożoność obliczeniowa jest zaledwie liniowo-logarytmiczna

Wady:

-    niestabilność algorytmu

-    wymagana określona struktura danych

-    ograniczony rozmiar zbioru danych (struktura statyczna).

-    stosunkowo trudna implementacja

-    dla małych zbiorów danych wolniejszy od QuickSort, ale szybszy niż MergeSort!

Zalety:

-    duża szybkość

-    bardzo mała wrażliwość na uporządkowanie

-    dla dużych zbiorów danych, szybszy nawet od QuickSort

-    wszystkie złożoności obliczeniowe (optymistyczna, pesymistyczna, oczekiwana)

takie same i klasy 0(n- log w)

-    złożoność pamięciowa jest stała 0(1)

-    sortowanie w miejscu

5