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

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

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.

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

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

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.

1.5. 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 CIterácia JavaRekurzia JavaIterácia Python3Rekurzia Python3

#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);
    }
}

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);
    }
}

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);
    }
}

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)

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)

Selection Sort

Prehľad

Selection Sort je triediaci algoritmus, ktorý rozdelí pole

Odkazy

Heap Sort:

https://en.wikipedia.org/wiki/Heapsort

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