SORTOWANIE PRZEZ KOPCOWANIE --HEAPSORT--

CO trzeba umieć:

-- TABLICE 

//////////////////////////////////////////////////////////////////
 

Sortowanie przez kopcowanie (heapsort) polega na tzw. budowaniu kopca następnie zamieniamy ostatni element z pierwszym. W ten sposób otrzymujemy jeden element posortowany, następnie budujemy kopiec dla tablicy, ale już o ten jeden element mniejszej, bo ten jeden element jest już na swoim miejscu (tak samo robiliśmy w quicksort-cie). Czynności te powtarzamy, aż braknie nam elementów w kopcu oznaczać to będzie, że wszystkie nasze elementy są we właściwych miejscach. Jasne ? I tak wiem, że nie :). No bo co to jest ten kopiec? Kopiec to takie drzewo zrównoważone (liście na takim drzewie są na poziomach nie większych od siebie o 1, czyli na 3 i 4, 7 i 7 lub 8 i 9, natomiast gdy są na poziomach 2 i 4 to już drzewo nie jest zrównoważone). No ale ja tu straszę drzewami, a przecież mieliśmy sortować tablicę, no i będziemy. Tylko tą naszą tablicę rozpiszemy sobie na właśnie takim drzewie, ale nie bój nic, to drzewo będzie tylko w naszej wyobraźni dla łatwiejszego zrozumienia, a tak naprawdę to wszystko będzie odbywać się na tablicy. No ale to nie wszystkie ciekawostki o kopcu. Kopiec ma jeszcze taką własność, że na samej górze ma największe elementy (lub najmniejsze zależy jak sortujemy). Kopiec ma tak ułożone elementy w tym naszym wyimaginowanym drzewku, że jak weźmiemy dowolny element na dowolnym poziome to pod nim nie będzie elementów większych od naszego elementu.

np.:

Dobrze, a teraz powolutku wszystko jeszcze raz od początku. Nasza tablica [5,2,8,1,4,3]. Zaczynamy od wyobrażenia sobie drzewka zbudowanego na podstawie naszej tablicy.

Tak właśnie powinniśmy sobie wyobrazić nasze drzewko.(Dziećmi elementu i indeksie 0 są elementy o indeksie 1 i 2, dziećmi elementu o indeksie 1 są elementy o indeksie 3 i 4, a dziećmi elementu o indeksie 2 są elementy o indeksie 5 i 6(tutaj nie ma)). W ogólności możemy zauważyć, że lewy potomek i-tego elementu ma indeks l=i*2+1 natomiast prawy potomek ma indeks r=i*2+2.

Następnie musimy zbudować kopiec. Kopiec budujemy w danym punkcie i zaczynamy od dołu poddrzewa, którego korzeniem jest nasz punkt, następnie idziemy w górę do naszego punktu, ale nie sprawdzamy własności kopca dla liści, gdyż nie miałoby to sensu, bo liście nie mają pod sobą żadnego elementu. Więc zaczynamy od elementu (8). (8) jest większe od 3 i od niczego czyli jest dobrze. Teraz sprawdzamy element (2). (2) jest większe od 1 ale mniejsze od 4 więc następuje zamiana.

[5,4,8,1,2,3]

Ale przez to, że dokonaliśmy zamiany mogliśmy popsuć nasz wcześniej zbudowany kopiec, więc musimy sprawdzić własność kopca dla elementu zamienionego, czyli o indeksie 4. Ten element jest naszym liściem, więc koniec sprawdzanie i wracamy dalej. Teraz sprawdzamy element (5). 4 mniejsze od 5, ale 8 większe od 5 więc zamieniamy.

[8,4,5,1,2,3]

Teraz ponownie musimy sprawdzić nasz kopiec w elemencie o indeksie 2. 5 jest większe od 3. Nie dokonujemy zamiany. Mamy masz kopiec.

Teraz dokonujemy zamiany elementów ostatni z pierwszym

[3,4,5,1,2,8]

Element o wartości (8) jest na swoim miejscu, więc nie bierze ponownego udziału w budowani kopca. A my ponownie wyobrażamy sobie nasze drzewko.

Następnie ponownie przywracam własności kopca dla punktu
o indeksie 0. Więc bierzemy element (4) (bo 2,1,5 to liście)
i sprawdzamy własności kopca. (1) i (2) są mniejsze od (4), więc jest dobrze. Teraz bierzemy element o kluczu (3) i sprawdzamy. Zarówno (4) i (5) są większe, więc wybieramy większy z nich i zamieniamy.

[5,4,3,1,2,8]

Zbudowaliśmy ponownie kopiec, więc możemy zamienić element pierwszy z elementem ostatnim (w kopcu) i otrzymamy kolejny element na swoim miejscu.

[2,4,3,1,5,8]

Teraz znowu działamy naszą wyobraźnią i imaginujemy sobie nowiuśkie drzewko.

Ponownie budujemy kopiec w punkcie o indeksie 0. (1) i (3) są liśćmi, więc sprawdzamy element (4). Jest OK. Sprawdzamy element (2) znowu (4) jak i (3) są większe, więc wybieramy jeden z nich i zamieniamy.

[4,2,3,1,5,8]

Teraz musimy jeszcze sprawdzić własność kopca dla zamienionego punktu, bo mogliśmy coś popsuć przesuwając mniejszy element do dołu. 2 jest większe od 1, więc mamy szczęście i wszystko jest w porządeczku. Teraz możemy znowu zamienić pierwszy element z ostatnim i mam kolejny element na swoim miejscu.

[1,2,3,4,5,8]

Budujemy drzewko z tego co zostało.

Zamieniamy (1) z (3), chyba już wiadomo dlaczego. (1) teraz jest liściem, więc OK.

[3,2,1,4,5,8]

Zamieniamy ostatni z pierwszym i budujemy ponownie drzewko.

[1,2,3,4,5,8]

Mamy już dwa elementy. (1) mniejsze od (2) zamieniamy.

[2,1,3,4,5,8]

Kopiec zbudowany, więc zamieniamy elementy miejscami i budujemy drzewo ponownie.

[1,2,3,4,5,8]

Teraz nam wyrósł jakiś badylec, a nie drzewo, ale jest bardzo dobrze :). W kopcu pozostał jeden element, więc kończymy, a otrzymana w ten sposób tablica jest uporządkowana.

[1,2,3,4,5,8]

Złożoność tego sortowania wynosi O[n log(n)], czyli tyle samo co Qsort.

KOD:

void przywroc (int tab[], int n, int i){

// funkcja przywraca własność kopca w punkcie o indeksie „i”

    int j=i,r=i*2+2,l=i*2+1; // zmienne pomocnicze

    if((l<n) && (tab[i]<tab[l])) j=l; // sprawdza czy relacje z lewym

    if((r<n) && (tab[j]<tab[r])) j=r; // sprawdza relacje z prawym

    if(i!=j){ // gdy chociaż ejdna realcja była źle

    // zamiana elementów

       int temp = tab[i];

       tab[i]=tab[j];

       tab[j]=temp;

   //

       przywroc(tab,n,j); // wywołanie funkcji w punkcie zamiany

    }

}

void build(int tab[],int n){

// funkcja buduje nam kopiec na samym początku

    int i; // zmienne pomocnicza

    for(i=(n-2)/2;i>=0;i--)przywroc(tab,n,i);
  // przywrócenie własności w każdym z punktów (bez liści)

}

void sort(int tab[],int n){

// funkcja główna (sortuje)

     int i,temp; // zmienne pomocnicze

     build(tab,n); // budowanie pierwszego kopca

     for( i=n-1;i>0;i--){
  // pętla którą będziemy po kolei wykluczać nasze elementy

  // zamiana pierwszego z ostatnim(który jest w kopcu)

          temp=tab[i];

          tab[i]=tab[0];

          tab[0]=temp;

    //

          przywroc(tab,i,0);
     // ponowne przywrócenie własności kopca dla punktu o indeksie 0

     }

}

Cały kod składa się z trzech funkcji. Pierwsza funkcja jest funkcją rekurencyjną, która przywraca własność kopca w punkcie. Sprawdza, czy relacja z lewym i prawym synem jest poprawna, jeśli nie to dokonana jest zamiana. A następnie ponownie wywołana jest funkcja przywracania własności kopca dla punktu zamiany, bo jeżeli z góry byśmy wzięli mały element to mógłby być on mniejszy od reszty elementów w tym poddrzewie, więc nie otrzymalibyśmy prawidłowego kopca. Dlatego potrzeba jest sprawdzenie własności dla tego elementu jeszcze raz. Funkcja build buduje nam pierwszy kopice, czyli przywraca własność kopca dla każdego elementu w tablicy oczywiście oprócz tych, które pełnią rolę liści. Funkcja sort jest główną funkcją naszego programu. Wywołuje ona naszą funkcję build, a następnie zamienia miejscami elementy pierwszy i ostatni, a następnie przywraca własność kopca dla tego elementu. Odpowiada za to pętla for, która wykonuje się gdy w kopcu nie zostanie już żaden element.