Triedenie výberom

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

>Triedenie výmenou
>Triedenie vkladaním
>Triedenie zlučovaním
>Triedenie delením
>Triedenie výberom
>Triedenie - ostatné princípy

Lineárny zoznam

Binárny strom

Numerické algoritmy

Grafové algoritmy

Tento článok je v prvotnom štádiu konštrukcie, zatiaľ je to len hromada myšlienok :)

odtiaľto sa odrazíme: https://en.wikipedia.org/wiki/Heapsort

Heap Sort

Prehľad

Heap Sort je triediaci algoritmus, ktorý na triedenie využíva dátovú štruktúru binárna hromada. Celé triedenie spočíva v tom, že si algoritmus vytvorí binárnu hromadu zo vstupného poľa a následne postupným mazaním všetkých jej prvkov toto pole utriedi.

Hromada, ktorú využíva algoritmus Heap Sort, musí spĺňať nasledovné podmienky (ak indexujeme pole od 0):

1. Vrchol hromady (koreň) je vždy prvý prvok v poli (v našom prípade prvok na 0-tej pozícii).

2. Pre ľubovoľný prvok (uzol), uložený na indexe [math]i[/math] z intervalu [math] \langle 0 \ ; \ \text{dĺžka} - 1 \rangle [/math], platia nasledovné rovnice:

[math] \begin{align} \text{ľavý potomok} &= 2i + 1 && (1) \\ \text{pravý potomok} &= 2i + 2 && (2) \\ \text{rodič} &= \left \lfloor \frac{i - 1}{2} \right \rfloor \quad (\text {okrem} \ i = 0) && (3) \end{align} [/math]

3. Každý prvok (uzol) v hromade musí mať väčšiu, alebo rovnakú hodnotu ako jeho potomkovia (MAX HEAP - ak triedime pole vzostupne, v opačnom prípade by sme použili MIN HEAP).

Algoritmus Heapify

vizualizácia

Heapify je kľúčovým podprogramom triediaceho algoritmu Heap Sort, vďaka ktorému vieme efektíve zabezpečiť vytvorenie hromady z poľa a zmazanie hromady.

Ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom funkcia Heapify zlúči tieto dve podhromady do jednej hromady, pričom i-ty prvok bude jej vrcholom.

Vlastnosti algoritmu

• dátová štruktúra: hromada (reprezentovaná ako: pole, strom)
• časová zložitosť: lineárna [math]O(n)[/math]
• priestorová zložitosť: konštantná [math]O(1)[/math] pri iteračnej verzii, [math]O(log(N))[/math] pri rekurzívnej verzii

Základné časti algoritmu

1. Určenie potomka s maximálnou hodnotou i-teho prvku.
2. Porovnanie maximálneho potomka s rodičom (i-tym prvkom).
3. Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
4. Ak nastala výmena, skontrolovanie ovplyvneného potomka (podstromu).

Slovný opis algoritmu

Dostaneme na vstupe pole a index i, v ktorom chceme vytvoriť hromadu. Najskôr skontrolujeme, či prvok na indexe i má nejakých potomkov (využijeme rovnice (1) a (2)). Ak nemá žiadnych potomkov, funkcia skončí, pretože i predstavuje jednoprvkovú hromadu. Ak má práve jedného potomka, tento potomok je zároveň maximálnym potomkom. Ak má práve dvoch potomkov, tak z nich vyberieme maximálneho potomka. Následne Skontrolujeme veľkosť maximálneho potomka a jeho rodiča (prvok na indexe i). Ak je rodič väčší, funkcia skončí, pretože prvok i predstavuje vrchol hromady. Ak nie, vymeníme rodiča a maximálneho potomka. Ak nastala výmena, musíme skontrolovať ovplyvnenú podhromadu, tj. zopakovať tento sled krokov pre podhromadu, ktorej vrchol bude v maximálnom potomkovi i-teho prvku.

Z hľadiska implementácie môžeme vytvoriť iteračnú aj rekurzívnu verziu.

Pseudokód

Iteračná verziaRekurzívna verzia

Nech funkcia Heapify má nasledovný prototyp Heapify(pole[], dlzka, i)

1. Je 2 * i + 1 < dlzka ? Ak áno, pokračuj krokom 1.1., inak skonči.

1.1. Nech: lavy = 2 * i + 1

1.2. Nech: pravy = 2 * i + 2

1.3. Je pravy < dlzka a zároveň pole[pravy] > pole[lavy] ?

Ak áno:

1.3.1. Nech: max = pravy

Ak nie:

1.3.1. Nech: max = lavy

1.4. Je pole[max] > pole[i] ?

Ak áno:

1.4.1. Vymeň: pole[max] a pole[i]

1.4.2. i = max

Ak nie:

1.4.1 Skonči.

2. Skoč na krok 1.

Nech funkcia Heapify má nasledovný prototyp Heapify(pole[], dlzka, i)

1. Je pole[2 * i + 1] >= pole[2 * i + 2] ?

Ak áno:

1.1. Nech: max = pole[2 * i + 1]

Ak nie:

1.1. Nech: max = pole[2 * i + 2]

2. Je pole[max] > pole[i] ?

Ak áno:

2.1. Vymeň: pole[i] a pole[max]

2.2. Rekurzívne zavolaj: Heapify(pole[], dlzka, max)

Ak nie:

2.1. Skonči volanie.

Algoritmus Heap Sort

Heapsort pri triedení vykonáva dve základné úlohy: Vytvorenie maximálnej binárnej hromady zo vstupného poľa a mazanie jednotlivých prvkov z hromady. Pri oboch procedúrach využíva algoritmus Heapify

Vlastnosti algoritmu

• vhodný pre dátové štruktúry: pole
• časová náročnosť: vždy linearitmická [math] O(n\log(n)) [/math], vďaka ktorej dokáže efektívne triediť veľmi veľké polia
• priestorová náročnosť: konštantná [math]O(1)[/math] pri iteračnej verzii, logaritmická [math]O(\log(n))[/math] pri rekurzívnej verzii.
• druh triedenia: triedenie výberom (komparačný algoritmus)
• stabilita triedenia: nestabilný
• miesto triedenia: vnútorné triedenie

Základné časti algoritmu

1. vytvorenie hromady
2. zmazanie hromady

Slovný opis

Vytvorenie hromady

Pri vytváraní hromady využijeme algoritmus heapify, pričom hromadu vytvoríme spôsobom zospodu na vrch. Najskôr si určíme prvok ktorý je najspodnejší a najviac vpravo a zároveň má aspoň jedného potomka. Tento prvok určíme veľmi jednoducho, pretože zpberieme posledný prvok v poli, a pomocou rovnice 3, ktorú si jemne upravíme mu nájdeme rodiča:

[math] \text{posledný rodič} = \left \lfloor \frac{\text{posledný index } - 1}{2} \right \rfloor = \left \lfloor\frac{\text{dĺžka } - 2}{2} \right \rfloor = \left \lfloor \frac{\text{dĺžka}}{2}\right \rfloor - 1 [/math]

Následne zavoláme Heapify na podhromadu s vrcholom posledného rodiča. Potom zmenšíme o 1 a opakujeme tento proces , až kým neprídeme na začiatok. Schematicky by sme to mohli napísať takto:

[math] \text{pre } i \text{ z intervalu } \left \langle \left \lfloor \frac {\text{dĺžka}}{2} \right \rfloor - 1 \quad ; \quad 0 \right \rangle :\ \text{heapify( pole[], dĺžka, i )}[/math]

Zmazanie hromady

Pri mazaní hromady vykonáme dve operácie. Ako prvé vymeníme prvok na vrchu hromady s koncovým prvkom hromady. Prvok čo je na komci považujeme za zmazaný, preto veľkosť hromady znížime o 1. Následne musíme zabezpečiť zachovanie pravidiel pre hromadu, takže zavoláme funkciu Heapify na celú hromadu (index i bude vrch hromady, čiže 0-tý prvok v poli). Tento proces opakujeme, poikiaľ v hromade neostanú žiadne prvky.

Poznámka: v našom prípade nemusíme mazať celú hromadu, ale iba do chvíle, keď nám neostane 1 prvok.

Schematicky by sme to mohli zapísať takto:

[math]\text{pre } j \text{ z intervalu } \left \langle \text{dĺžka - 1} \quad ; \quad 0 \right \rangle : \ \ \text{vymeň(pole[0], pole[$j$])} \ \ a \ \ \text{heapify(pole[], dĺžka, 0)} [/math]

Pseudokód

Nech funkcia Heap Sort má nasledovný prototyp: HeapSort(pole[], dlzka)

1. Nech: i = dlzka / 2 - 1, kde "/" predstavuje celočíslené delenie.

2. Je i >= 0 ? Ak áno, pokračuj krokom 2.1., inak skoč na krok 3.

2.1. Zavolaj funkciu Heapify(pole[], dlzka, i)

2.2. Skoč na krok 2.

3. Nech: j = dlzka - 1

4 Je j > 0 ? Ak áno, pokračuj krokom 4.1, inak skonči.

4.1. Vymeň: pole[0] a pole[j]

4.2. Zavolaj funkciu Heapify(pole[], dlzka, i)

4.3. Skoč na krok 4.

Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch

Iteračná CRekurzívna C

#include <stdio.h>

void Vymen(int *a, int *b);
void Heapify(int pole[], int dlzka, int index);
void HeapSort(int pole[], int dlzka);

int main()
{
    int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0, -1};
    int dlzka = sizeof(pole) / sizeof(pole[0]);

    HeapSort(pole, dlzka);

    for (int i = 0; i < dlzka; ++i)
    {
        printf("%d ", pole[i]);
    }
}


void Vymen(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Heapify(int pole[], int dlzka, int index)
{
    int pravy, lavy, max;

    while(2 * index + 1 < dlzka)
    {
        lavy = 2 * index + 1;
        pravy = 2 * index + 2;

        // určenie potomka s maximálnou hodnotou
        if(pravy < dlzka && pole[pravy] > pole[lavy])
        {
            max = pravy;
        }
        else
        {
            max = lavy;
        }

        // porovnanie maximálneho potomka s rodičom
        if(pole[max] > pole[index])
        {

            Vymen(&pole[max], &pole[index]);
            index = max;
        }
        else
        {
            return;
        }
    }
}

void HeapSort(int pole[], int dlzka)
{
    // vytvor  maximálnu hromadu (procedúra BuildMaxHeap)
    for (int i = dlzka / 2 - 1 ; i >= 0; --i)
    {
        Heapify(pole, dlzka, i);
    }

    // zmaž všetky prvky z hromady
    for (int j = dlzka - 1; j > 0; --j)
    {
        Vymen(&pole[0], &pole[j]);
        Heapify(pole, j, 0);
    }
}

#include <stdio.h>

void Vymen(int *a, int *b);
void Heapify(int pole[], int dlzka, int index);
void HeapSort(int pole[], int dlzka);

int main()
{
    int pole[]= {10, 5, 2, 9, 8, 7, 1, 3, 4, 0, -1, -1};
    int dlzka = sizeof(pole) / sizeof(pole[0]);

    HeapSort(pole, dlzka);

    for (int i = 0; i < dlzka; ++i)
    {
        printf("%d ", pole[i]);
    }
}


void Vymen(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void Heapify(int pole[], int dlzka, int index)
{

        int lavy = 2 * index + 1;
        int pravy = 2 * index + 2;
        int max = index;

        // určenie potomka s maximálnou hodnotou
        if(lavy < dlzka && pole[lavy] >= pole[pravy])
        {
            max = lavy;
        }

        if(pravy < dlzka && pole[pravy] > pole[lavy])
        {
            max = pravy;
        }

        // porovnanie maximálneho potomka s rodičom
        if(pole[max] > pole[index])
        {
            Vymen(&pole[max], &pole[index]);
            Heapify(pole, dlzka, max);
        }
}

void HeapSort(int pole[], int dlzka)
{
    // vytvor  maximálnu hromadu (procedúra BuildMaxHeap)
    for (int i = dlzka / 2 - 1 ; i >= 0; --i)
    {
        Heapify(pole, dlzka, i);
    }

    // zmaž všetky prvky z hromady
    for (int j = dlzka - 1; j > 0; --j)
    {
        Vymen(&pole[0], &pole[j]);
        Heapify(pole, j, 0);
    }
}

Selection Sort

Coming soon :)

Odkazy

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_heapify_method.htm