Sortowanie przez kopcowanie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Sortowanie przez kopcowanie
Heap sort example.gif
Animacja przedstawiająca działanie sortowania przez kopcowanie
Rodzaj Sortowanie
Struktura danych Kolejka priorytetowa
Złożoność
Czasowa \scriptstyle \mathrm O(n \log n)
Pamięciowa całkowita: \scriptstyle \mathrm O(n), pomocnicza: \scriptstyle \mathrm O(1)

Sortowanie przez kopcowanie (ang. heapsort) – jeden z algorytmów sortowania, choć niestabilny, to jednak szybki i niepochłaniający wiele pamięci (złożoność czasowa wynosi \scriptstyle \mathrm O(n \log n), a pamięciowa – \scriptstyle \mathrm O(n), przy czym jest to rozmiar sortowanych danych, złożoność pamięciowa dodatkowych struktur wynosi \scriptstyle \mathrm O(1); jest to zatem algorytm sortowania w miejscu). Jest on w praktyce z reguły nieco wolniejszy od 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)[1].

Opis algorytmu[edytuj | edytuj kod]

Information icon.svg Osobne artykuły: kopiec (informatyka)kopiec binarny.

Podstawą algorytmu jest użycie kolejki priorytetowej zaimplementowanej w postaci binarnego 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 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[edytuj | edytuj kod]

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:

kopiec reszta nieposortowanych elementów

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(nlog 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:

reszta nieposortowanych elementów małe kopce

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:

 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

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

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

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

Sortowanie[edytuj | edytuj kod]

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:

kopiec elementów do posortowania posortowana tablica

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(nlog n).

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

Prezentację takiego sortowania można zobaczyć na stronie Sortowanie przez kopcowanie. Ta strona zawiera applet prezentujący działanie procedury budującej kopiec z danych zawartych w tablicy oraz umożliwia podgląd zawartości tablicy w postaci drzewa.

Implementacja[edytuj | edytuj kod]

Powyższy pseudokod zaimplementowany w Pascalu będzie miał postać:

{$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 moze 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[edytuj | edytuj kod]

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żność 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