Triedenie zlučovaním: Rozdiel medzi revíziami
| Riadok 5: | Riadok 5: | ||
| − | ==Merge | + | ==Zlučovacia funkcia Merge:== |
| − | |||
| − | |||
| − | |||
| − | + | Funkcia Merge je zlučovacia funkcia, ktorá tvorí základ triediaceho algoritmu Merge sort. | |
| − | + | ===Princíp zlučovania:=== | |
Vo všeobecnosti princíp zlučovania tkvie v tom, že zoberieme dva (alebo viac) menšie utriedné zoznamy, ktoré skombinujeme do jedného väčšieho utriedeného zoznamu. Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tejto časti sa zameriame na algoritmus pre dátovú štruktúru pole. | Vo všeobecnosti princíp zlučovania tkvie v tom, že zoberieme dva (alebo viac) menšie utriedné zoznamy, ktoré skombinujeme do jedného väčšieho utriedeného zoznamu. Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tejto časti sa zameriame na algoritmus pre dátovú štruktúru pole. | ||
| − | + | ===Slovný opis algoritmu:=== | |
Pri funkcii Merge využívame princíp zlučovania tak, že máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Následne si vytvoríme dve pomocné polia, do ktorých skopíruje obsahy oboch polovíc. Potom súčasne prechádzame obe pomocné polia a vždy z uvažovanej dvojice prvkov vyberáme ten menší z nich (keď triedime od najväčšieho po najmenší) a vložíme ho na začiatok pôvodného poľa. Index zvýšime iba pri tom poli z ktorého sme daný prvok vybrali. Ak nastane situácia, že z jedného pomocného poľa vyberieme všetky prvky skôr, ako z druhého pomocného poľa, potom zbytok druhého pomocného poľa už iba kopírujeme na koniec pôvodného poľa. | Pri funkcii Merge využívame princíp zlučovania tak, že máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Následne si vytvoríme dve pomocné polia, do ktorých skopíruje obsahy oboch polovíc. Potom súčasne prechádzame obe pomocné polia a vždy z uvažovanej dvojice prvkov vyberáme ten menší z nich (keď triedime od najväčšieho po najmenší) a vložíme ho na začiatok pôvodného poľa. Index zvýšime iba pri tom poli z ktorého sme daný prvok vybrali. Ak nastane situácia, že z jedného pomocného poľa vyberieme všetky prvky skôr, ako z druhého pomocného poľa, potom zbytok druhého pomocného poľa už iba kopírujeme na koniec pôvodného poľa. | ||
| − | + | ===Vzorový príklad:=== | |
| − | Máme pole prvkov p = [1, 3, 5, 2, 4, 6], ktoré je už čiastočne utriedené. Použijeme algoritmus Merge, ktorý si vyptvorí pomocné polia p1 = [1, 3, 5] a p2 = [2, 4, 6]. Všetky polia indexujeme od 0, pričom pre pole p používame index k, pre p1 index i a p2 index j. | + | Máme pole prvkov p = [1, 3, 5, 2, 4, 6], ktoré je už čiastočne utriedené. Použijeme algoritmus Merge, ktorý si vyptvorí pomocné polia p1 = [1, 3, 5] a p2 = [2, 4, 6]. Všetky polia indexujeme od 0, pričom pre pole p používame index k, pre p1 index i a p2 index j. |
| + | |||
| + | ===Pseudokód=== | ||
| + | Nech funkcia Merge má parametre, pole[], lavy, stred a pravy. | ||
| + | # Nech i = 0, j = 0, k = 0 | ||
| + | # | ||
| + | |||
| Riadok 27: | Riadok 30: | ||
[[Súbor:Funkcia merge.png|1100px|náhľad|stred|Vizualizácia funkcie Merge]] | [[Súbor:Funkcia merge.png|1100px|náhľad|stred|Vizualizácia funkcie Merge]] | ||
| + | |||
| + | |||
| + | ==Merge sort== | ||
| + | Merge Sort je triediaci algoritmus, ktorý je založený na princípe '''"rozdeľ a panuj"''', čo znamená, že pole najskôr rozdelí na dve polovice, tie zoradí a potom ich zlúči naspäť dokopy. Keďže najhoršia doba výpočtu je <math>O(n.log(n))</math>, tak sa radí medzi najpoužívanejšie a najviac rešpektované triediacie algoritmy. | ||
| + | ===Princíp algoritmu=== | ||
| + | Algoritmus Merge sort má dve časti | ||
| + | Základom algoritmu | ||
Verzia zo dňa a času 18:20, 22. marec 2021
Obsah
Zlučovacia funkcia Merge:
Funkcia Merge je zlučovacia funkcia, ktorá tvorí základ triediaceho algoritmu Merge sort.
Princíp zlučovania:
Vo všeobecnosti princíp zlučovania tkvie v tom, že zoberieme dva (alebo viac) menšie utriedné zoznamy, ktoré skombinujeme do jedného väčšieho utriedeného zoznamu. Zoznam môže byť reprezentovaný ako dátová štruktúra pole alebo aj ako lineárny zoznam. V tejto časti sa zameriame na algoritmus pre dátovú štruktúru pole.
Slovný opis algoritmu:
Pri funkcii Merge využívame princíp zlučovania tak, že máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Následne si vytvoríme dve pomocné polia, do ktorých skopíruje obsahy oboch polovíc. Potom súčasne prechádzame obe pomocné polia a vždy z uvažovanej dvojice prvkov vyberáme ten menší z nich (keď triedime od najväčšieho po najmenší) a vložíme ho na začiatok pôvodného poľa. Index zvýšime iba pri tom poli z ktorého sme daný prvok vybrali. Ak nastane situácia, že z jedného pomocného poľa vyberieme všetky prvky skôr, ako z druhého pomocného poľa, potom zbytok druhého pomocného poľa už iba kopírujeme na koniec pôvodného poľa.
Vzorový príklad:
Máme pole prvkov p = [1, 3, 5, 2, 4, 6], ktoré je už čiastočne utriedené. Použijeme algoritmus Merge, ktorý si vyptvorí pomocné polia p1 = [1, 3, 5] a p2 = [2, 4, 6]. Všetky polia indexujeme od 0, pričom pre pole p používame index k, pre p1 index i a p2 index j.
Pseudokód
Nech funkcia Merge má parametre, pole[], lavy, stred a pravy.
- Nech i = 0, j = 0, k = 0
Merge sort
Merge Sort je triediaci algoritmus, ktorý je založený na princípe "rozdeľ a panuj", čo znamená, že pole najskôr rozdelí na dve polovice, tie zoradí a potom ich zlúči naspäť dokopy. Keďže najhoršia doba výpočtu je [math]O(n.log(n))[/math], tak sa radí medzi najpoužívanejšie a najviac rešpektované triediacie algoritmy.
Princíp algoritmu
Algoritmus Merge sort má dve časti Základom algoritmu
