Zobrazenie zdroja stránky Triedenie výberom

[[Kategória:Algoritmy triedenia]]
{{Draft}}
{{Skripta programovanie}}
__TOC__
==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ý podobne ako Selection sort rozeľuje pole na zotriedenú a nezotriedenú časť, pričom  nezotriedená časť predstavuje dátovú štruktúru [[Hromada|binárna hromada]]. Celé triedenie spočíva v tom, že si zo vstupného poľa vytvoríme binárnu hromadu a následne postupným vyberaním  a mazaním všetkých jej prvkov toto pole utriedime.
 
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=== 
[[Súbor:Heapify.png|vizualizácia|699px|náhľad|vpravo]]
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. 

Princíp algoritmu Heapify spočíva v tom, že ak máme i-ty prvok v poli (v kompletnom binárnom strome), ktorého potomkovia tvoria dve samostatné podhromady, potom tieto dve podhromady zlúčime 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====
# Určenie potomka s maximálnou hodnotou i-teho prvku.
# Porovnanie maximálneho potomka s rodičom (i-tym prvkom).
# Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
# Ak nastala výmena, skontrolovanie ovplyvneného potomka (podhromady).

====Slovný opis algoritmu====
Na vstupe prijmeme pole a index i, v ktorom chceme vytvoriť hromadu (Max Heap). Najskôr skontrolujeme, či prvok na indexe i má nejakých potomkov (využijeme rovnice (1) a (2) z časti "Prehľad"). Ak nemá žiadnych potomkov, funkcia skončí, pretože i predstavuje vrchol jednoprvkovej hromady. Ak má práve jedného potomka, tento potomok je zároveň jeho maximálnym potomkom. Ak má práve dvoch potomkov, tak  porovnáme ich hodnoty a vyberieme z nich 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 želaná hromada už je utvorená. 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====
<tabs>
<tab name="Iteračná verzia" block>
Nech funkcia Heapify má nasledovný prototyp: <code>Heapify(pole[], dlzka, i)</code>
:1. Je <code>2 * i + 1 < dlzka</code> ? Ak áno, pokračuj krokom 1.1., inak skonči.
:::1.1. Nech: <code>lavy = 2 * i + 1</code>
:::1.2. Nech: <code>pravy = 2 * i + 2</code>
:::1.3. Je <code>pravy < dlzka</code> a zároveň <code>pole[pravy] > pole[lavy]</code> ?
:::::Ak áno: 
:::::::1.3.1. Nech: <code>max = pravy</code>
:::::Ak nie:
:::::::1.3.1. Nech: <code>max = lavy</code>
:::1.4. Je <code>pole[max] > pole[i]</code> ?
:::::Ak áno:
:::::::1.4.1. Vymeň: <code>pole[max]</code> a <code>pole[i]</code>
:::::::1.4.2. <code>i = max</code>
:::::Ak nie: 
:::::::1.4.1 Skonči.
:::1.5. Skoč na krok 1.

</tab>

<tab name="Rekurzívna verzia" block>
Nech funkcia Heapify má nasledovný prototyp: <code>Heapify(pole[], dlzka, i)</code>
:1. Je <code>pole[2 * i + 1] >= pole[2 * i + 2]</code> ?
::: Ak áno:
:::::1.1. Nech: <code>max = pole[2 * i + 1]</code> 
::: Ak nie:
:::::1.1. Nech: <code>max = pole[2 * i + 2]</code> 
:2. Je <code>pole[max] > pole[i]</code> ? 
::: Ak áno:
::::: 2.1. Vymeň: <code>pole[i] a pole[max]</code>
::::: 2.2. Rekurzívne zavolaj: <code>Heapify(pole[], dlzka, max)</code>
::: Ak nie:
::::: 2.1. Skonči volanie.
</tab>
</tabs>

===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

[[Súbor:HeapSort.png|500px|náhľad|vpravo]]

* 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====
# vytvorenie hromady
# 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: <center><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></center>
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:
<center><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></center>

=====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:
<center><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></center>


====Pseudokód====
Nech funkcia Heap Sort má nasledovný prototyp: <code>HeapSort(pole[], dlzka)</code> 

:1. Nech: <code>i = dlzka / 2 - 1</code>, kde "/" predstavuje celočíslené delenie.
:2. Je <code>i >= 0</code> ? Ak áno, pokračuj krokom 2.1., inak skoč na krok 3.
:::2.1. Zavolaj funkciu <code>Heapify(pole[], dlzka, i)</code>
:::2.2. Skoč na krok 2.
:3. Nech: <code>j = dlzka - 1</code>
:4 Je <code> j > 0</code> ? Ak áno, pokračuj krokom 4.1, inak skonči.
:::4.1. Vymeň: <code>pole[0]</code> a <code>pole[j]</code>
:::4.2. Zavolaj funkciu <code>Heapify(pole[], dlzka, i)</code>
:::4.3. Skoč na krok 4.

===Implementácia algoritmov Heapify a HeapSort v rôznych programovacích jazykoch===
<tabs>
<tab name="Iteračná C" block>
<syntaxhighlight lang="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);
    }
}
</syntaxhighlight>
</tab>
<tab name="Rekurzívna C" block>
<syntaxhighlight lang="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, -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);
    }
}
</syntaxhighlight>
</tab>

<tab name="Iterácia Java" block>
<syntaxhighlight lang="Java">
class HeapSortIT {
    void swap(int[] pole, int a, int b) {
        int tmp = pole[a];
        pole[a] = pole[b];
        pole[b] = tmp;
    }

    void heapify(int[] pole, int n) {
        for (int i = 1; i < n; i++) {

            /* Ak je potomok väčší ako rodič */
            if (pole[i] > pole[(i - 1) / 2]) {
                int j = i;

                /* Vymieňaj elementy (rodič, potomok), dokým je rodič menší ako potomok */
                while (pole[j] > pole[(j - 1) / 2]) {
                    swap(pole, j, (j - 1) / 2);
                    j = (j - 1) / 2;
                }
            }
        }
    }

    void sort(int[] pole) {
        int n = pole.length;

        heapify(pole, n);

        for (int i = n - 1; i > 0; i--) {
            int j = 0, index;

            /* Vymeň prvý a posledný prvok */
            swap(pole, 0, i);

            do {
                index = 2 * j + 1;

                /* Ak je ľavý potomok menši ako pravý, presuň 'index' na pravého potomka */
                if (index < i - 1 && pole[index] < pole[index + 1])
                    index++;

                /* Ak je rodič menší ako potomok, tak ho vymeň s potomkom, ktorý má väčšiu hodnotu */
                if (index < i && pole[j] < pole[index])
                    swap(pole, j, index);

                j = index;
            } while (index < i);
        }
    }
}

public class Main {

    static void printArray(int[] pole) {
        int n = pole.length;

        for (int i : pole)
            System.out.print(i + " ");

        System.out.println();
    }

    public static void main(String[] args) {
	    int[] pole = {12, 11, 13, 5, 6, 7};
	    int n = pole.length;

        System.out.println("Pole pred zoradenim: ");
        printArray(pole);

	    HeapSortIT hs = new HeapSortIT();
	    hs.sort(pole);

        System.out.println("Pole po zoradeni: ");
        printArray(pole);
    }
}
</syntaxhighlight>
</tab>

<tab name="Rekurzia Java" block>
<syntaxhighlight lang="Java">
class HeapSortRE {
    void swap(int[] pole, int a, int b) {
        int tmp = pole[a];
        pole[a] = pole[b];
        pole[b] = tmp;
    }
    
    void heapify(int[] pole, int n, int i) {
        int max = i; // rodič
        int l = 2 * i + 1; // ľavý potomok
        int p = 2 * i + 2; // pravý potomok

        /* Ak je ľavý potomok väčší ako rodič */
        if (l < n && pole[l] > pole[max])
            max = l;

        /* Ak je pravý potomok väčší ako rodič */
        if (p < n && pole[p] > pole[max])
            max = p;

        /* Ak sa rodič v priebehu funkcie zmenil */
        if (max != i) {
            swap(pole, i, max);

            heapify(pole, n, max);
        }
    }

    public void sort(int[] pole) {
       int n = pole.length;

       /* Vytvorenie hromadu */
        for (int i = n / 2 - 1; i >= 0 ; i--)
            heapify(pole, n, i);

        /* Extrahovanie jednotlivých elemetov z hromady */
        for (int i = n - 1; i > 0; i--) {
            /* Presuň aktuálneho rodiča na koniec */
            swap(pole, 0, i);

            /* Zavolanie heapify na zredukovanú hromadu */
            heapify(pole, i, 0);
        }
    }
}

public class Main {

    static void printArray(int[] pole) {
        int n = pole.length;

        for (int i : pole)
            System.out.print(i + " ");

        System.out.println();
    }

    public static void main(String[] args) {
	    int[] pole = {12, 11, 13, 5, 6, 7};
	    int n = pole.length;

        System.out.println("Pole pred zoradenim: ");
        printArray(pole);

	    HeapSortRE hs = new HeapSortRE();
	    hs.sort(pole);

        System.out.println("Pole po zoradeni: ");
        printArray(pole);
    }
}
</syntaxhighlight>
</tab>

<tab name="Iterácia Python3" block>
<syntaxhighlight lang="Python3">
def heapify(pole, n):
    for i in range(n):

        # Ak je potomok väčší ako rodič
        if pole[i] > pole[int((i - 1) / 2)]:
            j = i

            # Vymieňaj elementy (rodič, potomok), dokým je rodič menší ako potomok
            while pole[j] > pole[int((j - 1) / 2)]:
                pole[j], pole[int((j - 1) / 2)] = pole[int((j - 1) / 2)], pole[j]       # swap
                j = int((j - 1) / 2)


def sort(pole, n):
    heapify(pole, n)

    for i in range(n - 1, 0, -1):

        # Vymeň prvý a posledný prvok
        pole[0], pole[i] = pole[i], pole[0]     # swap

        j, index = 0, 0

        while True:
            index = 2 * j + 1

            # Ak je ľavý potomok menši ako pravý, presuň 'index' na pravého potomka
            if index < (i - 1) and pole[index] < pole[index + 1]:
                index += 1

            # Ak je rodič menší ako potomok, tak ho vymeň s potomkom, ktorý má väčšiu hodnotu
            if index < i and pole[j] < pole[index]:
                pole[j], pole[index] = pole[index], pole[j]     # swap

            j = index

            if index >= i:
                break


def printArray(pole, n):
    for i in range(n):
        print(pole[i], end=" ")


if __name__ == '__main__':
    pole = [12, 11, 13, 5, 6, 7]
    n = len(pole)

    print("Zadane pole:")
    printArray(pole, n)

    sort(pole, n)

    print("\nZoradene pole:")
    printArray(pole, n)

</syntaxhighlight>
</tab>

<tab name="Rekurzia Python3" block>
<syntaxhighlight lang="Python3">
def heapify(pole, n, i):
    max = i     # rodic
    l = 2 * i + 1       # lavy potomok
    p = 2 * i + 2       # pravy potomok

    # Ak je ľavý potomok väčší ako rodič
    if l < n and pole[max] < pole[l]:
        max = l

    # Ak je pravý potomok väčší ako rodič
    if p < n and pole[max] < pole[p]:
        max = p

    # Ak sa rodič v priebehu funkcie zmenil
    if max != i:
        pole[i], pole[max] = pole[max], pole[i]     # swap

        heapify(pole, n, max)


def sort(pole):
    n = len(pole)

    # Vytvorenie hromady
    for i in range(n // 2 - 1, -1, -1):
        heapify(pole, n, i)

    # Extrahovanie jednotlivých elementov z hromady
    for i in range(n - 1, 0, -1):
        pole[i], pole[0] = pole[0], pole[i]     # swap
        heapify(pole, i, 0)


def printArray(pole):
    n = len(pole)

    for i in range(n):
        print(pole[i], end=" ")


if __name__ == '__main__':
    pole = [12, 11, 13, 5, 6, 7]

    print("Zadane pole:")
    printArray(pole)

    sort(pole)

    print("\nZoradene pole:")
    printArray(pole)
</syntaxhighlight>
</tab>
</tabs>

==Selection Sort==
Coming soon :)

==Odkazy==
Heap Sort:

https://www.tutorialspoint.com/design_and_analysis_of_algorithms/design_and_analysis_of_algorithms_heapify_method.htm
https://www.geeksforgeeks.org/heap-sort/
https://www.geeksforgeeks.org/iterative-heap-sort/
https://www.youtube.com/watch?v=H5kAcmGOn4Q