procedure sort; var i: integer; aux: TElem; begin for i:=Size downto 2 do begin aux:=T; T:=T[i]; T[i]:=aux; shift_down(i-1,1); Assert(check_heap(i-1));//to może spowalniać end; end;
//możliwość wypełnienia innymi danymi np. po powiększeniu rozmiaru tablicy procedure random_init; var i: integer; begin for i:=1 to Size do T[i]:=random(Size); end;
begin //random_init; build_heap; Assert(check_heap(Size)); sort; end.
Porównanie z innymi algorytmami sortowania Algorytm sortowania przez kopcowanie jest na ogół nieco wolniejszy niż sortowanie szybkie. Jego przewagą natomiast jest lepsza złożoność pesymistyczna wynosząca O(n log n), podczas gdy dla quicksort jest to O(n2), co jest nie do przyjęcia dla dużych zbiorów danych. Także złożoność pamięciowa O(1) jest lepsza niż Ω(log n) algorytmu quicksort.
Heapsort jest nieco wolniejszy od algorytmu sortowania przez scalanie (mergesort), mającego taką samą asymptotyczną złożoność czasową. Mergesort wymaga jednak Ω(n) dodatkowej pamięci. Zaletą mergesort jest prostsza definicja i lepsze zachowanie w przypadkach, gdy dane do sortowania pobierane są z wolnej pamięci masowej; jest też łatwiejszy do zrównoleglenia.
Przypisy
Kopcowanie