1800320375

1. Opis i charakterystyka algorytmu.

Algorytm sortowania stogowego, zwany również algorytmem sortowanie przez kopcowanie (Heap Sort) jest jednym z najciekawszych narzędzi sortujących. Opiera się on na drzewiastej strukturze danych zwanej stertą, stogiem lub kopcem. Kopiec jest strukturą o kilku ważnych cechach, o których należy wspomnieć aby wytłumaczyć istotę sortowania stogowego. Własności kopca:

•    wartości potomków danego węzła są w stałej relacji z wartością rodzica

(dla kopca typu max wartość rodzica jest zawsze większa od wartości potomka, dla kopca typu min odwrotnie).

•    Jeżeli kopiec ma być kopcem zupełnym, wtedy dodatkowo spełnione muszą być warunki:

1.    drzewo jest prawie pełne tzn. liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie

2.    liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej.

•    Jeżeli implementujemy kopiec na tablicy i wybieramy węzeł o indeksie /, to jego lewy potomek będzie miał indeks 2i+l prawy natomiast 2i+2 (w numeracji od 0 do n)

Poprawnie zbudowany kopiec:

Rys.l Poprawnie zbudowany kopiec

Heap Sort będący algorytmem prawie tak szybkim jak Quick Sort (a w przypadku pesymistycznym, nawet szybszym!), jest praktycznie nie wrażliwy na uporządkowanie danych wejściowych. Jego złożoność obliczeniowa (czasowa) wynosi:

•    Złożoność optymistyczna:    O(n-logn)

•    Złożoność oczekiwana:    0(n • log ń)

•    Złożoność pesymistyczna:    O(n-\ogri)

Taki rodzaj złożoności jest spowodowany wywoływaniem procedur Bttild-Mcnc-Heap (utwórz kopiec o własności typu max), która jest złożoności jest klasy 0(n) oraz Mcnc-Heapify (przywróć danym zawartym w strukturze własność kopca typu max), która jest złożoności 0( log«).

Złożoność pamięciowa jest klasy 0(1) Heap Sort zawdzięcza to temu, iż jest tzw. algorytmem sortującym w miejscu. Oznacza to, iż w czasie procesu sortowania tylko stała

2