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

Algoritmus Heap Sort pri triedení využíva dátovú štruktúru binárna hromada, ktorú si vytvorí zo vstupného poľa, ktoré máme utriediť a následne zmazaním všetkých jej prvkov dosiahneme utriedené pole.

Hromada, ktorú vytvoríme musí spĺňať nasledovné podmienky:

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

2. Pre ľubovoľný prvok 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 od vzostupne).

Algoritmus Heapify

Heapify je kľúčovým podprogramom triediaceho algoritmu Heap Sort.

Základné časti algoritmu

1. Určenie maxima z 2 potomkov i-teho prvku a porovnanie s veľkosťou rodiča.
2. Ak je potomok väčší ako rodič, tak výmena potomka a rodiča.
3. Skontrolovanie ovplyvneného potomka (podstromu).

Slovný opis algoritmu

Ak máme i-ty prvok v poli, pričom oba jeho 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 (pole)
• č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

Rekurzívna verziaIteračná verzia

Pseudokód

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

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.

Odkazy

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