Tekst źródłowy strony Sortowanie przez kopcowanie

{{Algorytm infobox
 |nazwa            = Sortowanie przez kopcowanie
 |grafika          = Heap sort example.gif
 |wielkość grafiki = 
 |opis grafiki     = Animacja przedstawiająca działanie sortowania przez kopcowanie
 |rodzaj           = [[Sortowanie]]
 |struktura        = [[Kolejka priorytetowa]]
 |czas             = <math>O(n \log n)</math>
 |pamięć           = całkowita: <math>O(n)</math><br />pomocnicza: <math>O(1)</math>
}}
'''Sortowanie przez kopcowanie''' ([[język angielski|ang.]] ''heapsort''), zwane również '''sortowaniem stogowym'''<ref>[http://www.home.umk.pl/~abak/wdimat/s/HeapSort.html Sortowanie stogowe] w ''Algorytmy sortowania. Opis i demonstracja''.</ref> – jeden z [[algorytm]]ów [[sortowanie|sortowania]], choć [[sortowanie#Klasyfikacja|niestabilny]], to jednak szybki i niepochłaniający wiele [[pamięć|pamięci]] ([[złożoność obliczeniowa|złożoność]] czasowa wynosi <math>\mathrm O(n \log n),</math> a pamięciowa – <math>\mathrm O(n),</math> przy czym jest to rozmiar sortowanych danych, złożoność pamięciowa dodatkowych struktur wynosi <math>\mathrm O(1);</math> jest to zatem algorytm sortowania ''w miejscu''). Jest on w praktyce z reguły nieco wolniejszy od [[sortowanie szybkie|sortowania szybkiego]], lecz ma lepszą pesymistyczną złożoność czasową (przez co jest odporny np. na atak za pomocą celowo spreparowanych danych, które spowodowałyby jego znacznie wolniejsze działanie)<ref>{{Cytuj | url = http://igoro.com/archive/quicksort-killer/ | tytuł = Quicksort killer<!-- Tytuł wygenerowany przez bota --> | opublikowany = igoro.com | język = en | data dostępu = 2023-02-20}}</ref>.

== Opis algorytmu ==
{{osobny artykuł|kopiec (informatyka)|kopiec binarny}}
Podstawą algorytmu jest użycie [[kolejka priorytetowa|kolejki priorytetowej]] zaimplementowanej w postaci ''binarnego [[Kopiec (informatyka)|kopca]] zupełnego''. Zasadniczą zaletą kopców jest stały [[czas dostępu]] do elementu maksymalnego (lub minimalnego) oraz logarytmiczny czas wstawiania i usuwania elementów; ponadto łatwo można go implementować w postaci [[tablica (informatyka)|tablicy]].

Algorytm sortowania przez kopcowanie składa się z dwóch faz. W pierwszej sortowane elementy reorganizowane są w celu utworzenia kopca. W drugiej zaś dokonywane jest właściwe sortowanie.

=== Tworzenie kopca ===
Podstawową zaletą algorytmu jest to, że do stworzenia kopca wykorzystać można tę samą tablicę, w której początkowo znajdują się nieposortowane elementy. Dzięki temu uzyskuje się stałą złożoność pamięciową.

Początkowo do kopca należy tylko pierwszy element w tablicy. Następnie kopiec rozszerzany jest o drugą, trzecią i kolejne pozycje tablicy, przy czym przy każdym rozszerzeniu, nowy element jest przemieszczany w górę kopca, tak aby spełnione były relacje pomiędzy węzłami. Schematycznie wygląd sortowanej tablicy można przedstawić w następujący sposób:

<center>
{| class="wikitable" style="text-align:center;padding:30px;width:400px;height:40px"
| style="width:30%"| kopiec
| style="width:70%"| reszta nieposortowanych elementów
|}
</center>

a kopiec rozrasta się, aż do wyczerpania nieposortowanej części tablicy.

Dzięki logarytmicznej złożoności pojedynczych operacji wstawiania (rozszerzania kopca), całkowita złożoność tego etapu to ''O''(''n''&nbsp;log&nbsp;''n'').

Można też ten krok wykonać szybciej – w czasie ''O''(''n''). W tym celu należy budować kopiec w następujący sposób:

<center>
{| class="wikitable" style="text-align:center;padding:2em;width:400px;height:40px"
| style="width:70%"| reszta nieposortowanych elementów
| style="width:30%"| małe kopce
|}
</center>

Aby osiągnąć taką strukturę, wystarczy pierwsze ''n'' div 2 elementów tablicy (zakładając, że kopiec implementujemy w tablicy) przesunąć w dół kopca procedurą ''shift-down'':

<pre>
 shift-down (T[1..n], i)
     k ← i
     repeat
         j ← k
         if 2j <= n and T[2j] > T[k]
             k ← 2j
         if 2j+1 <= n and T[2j+1] > T[k]
             k ← 2j+1
         swap (T[j], T[k])
     until j = k
</pre>

Zatem procedura budująca kopiec wyglądałaby następująco:

<pre>
 build-heap (T[1..n])
     for i ← n div 2 downto 1
         shift-down (T, i)
</pre>

Procedura build-heap buduje kopiec w czasie ''O''(''n'').

=== Sortowanie ===
Po utworzeniu kopca następuje właściwe sortowanie. Polega ono na usunięciu wierzchołka kopca, zawierającego element maksymalny (minimalny), a następnie wstawieniu w jego miejsce elementu z końca kopca i odtworzenie porządku kopcowego. W zwolnione w ten sposób miejsce, zaraz za końcem zmniejszonego kopca wstawia się usunięty element maksymalny. Operacje te powtarza się aż do wyczerpania elementów w kopcu. Wygląd tablicy można tu schematycznie przedstawić następująco:

<center>
{| class="wikitable" style="text-align:center;padding:30px;width:400px;height:40px"
| style="width:70%"| kopiec elementów do posortowania
| style="width:30%"| posortowana tablica
|}
</center>

Tym razem kopiec kurczy się, a tablica przyrasta (od elementu ostatniego do pierwszego).

W tej fazie wykonuje się, jak w poprzedniej, ''n'' kroków (usuwanie elementu połączone z odtwarzaniem porządku kopcowego), każdy o koszcie logarytmicznym, zatem złożoność tej fazy to także ''O''(''n''&nbsp;log&nbsp;''n'').

<pre>
 sort (T[1..n])
     for i ← n downto 2
         swap (T[1], T[i])
         shift-down (T[1..i-1], 1)
</pre>

== Implementacja ==
Powyższy [[pseudokod]] zaimplementowany w Pascalu będzie miał postać:
<syntaxhighlight lang="pascal">
{$APPTYPE CONSOLE}
type
  TElem = integer;
const
  Size = 13;
var
  T:array[1..Size] of TElem = (4,1,3,2,16,9,10,14,8,7,99,78,55);

//procedura testowa sprawdzająca czy dane mają postać kopca
function check_heap(n: integer): boolean;
var
  i: integer;
begin
  result:=false;
  for i:=2 to n do
  if T[i]>T[i div 2] then exit;
  result:=true;
end;

procedure shift_down(n,i: integer);
var
  j,k: integer;
  aux: TElem;
begin
  k := i;
  repeat
    j := k;
    if (2*j <= n) and (T[2*j] > T[k]) then
       k := 2*j;
    if (2*j+1 <= n) and (T[2*j+1] > T[k]) then
       k := 2*j+1;
    aux:=T[j];
    T[j]:=T[k];
    T[k]:=aux;
  until j = k;
end;

procedure build_heap;
var
  i: integer;
begin
  for i := Size div 2 downto 1 do
    shift_down (Size,i);
end;

procedure sort;
var
  i: integer;
  aux: TElem;
begin
  for i:=Size downto 2 do
  begin
    aux:=T[1];
    T[1]:=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.
</syntaxhighlight>

== 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''&nbsp;log&nbsp;''n''), podczas gdy dla quicksort jest to ''O''(''n''<sup>2</sup>), 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&nbsp;''n'') algorytmu quicksort.

Heapsort jest nieco wolniejszy od algorytmu [[sortowanie przez scalanie|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 ==
{{Przypisy}}

{{Algorytmy sortowania}}

[[Kategoria:Algorytmy sortowania|Kopcowanie]]

[[no:Sorteringsalgoritme#Heap sort]]