Triedenie zlučovaním

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

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.

Vizualizácia funkcie Merge

Pseudokód

Nech funkcia Merge má parametre, pole[], lavy, stred a pravy.

1. Nech: i = 0, j = 0, k = 0

2. Nech: p1 = pole[lavy ... stred], p2 = pole[stred + 1 ... pravy]

3. Je i <= (stred - lavy) a zároveň j < (pravy - stred) ? Ak áno, pokračuj krokom 3.1., inak skok na krok 4.

3.1. Je p1[i] <= p2[j]? Ak áno, pole[k++] = p1[i++], inak pole[k++] = p2[j++].

3.2. Skok na krok 3.

4. Je i <= (stred - lavy) ? Ak áno, pokračuj krokom 4.1., inak skok na krok 5.

4.1. pole[k++] = p1[i++]

4.2. Skok na krok 4.

5. Je j < (pravy - stred) ? Ak áno, pokračuj krokom 5.1., inak skonči program.

5.1. pole[k++] = p2[j++]

5.2. Skok na krok 5.

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 vykonáva 3 základné úlohy:

1. Delenie poľa na dve polovice.
2. Triedenie ľavej polovice poľa.
3. Triedenie pravej polovice poľa.
4. Zlúčenie oboch polovíc pomocou funkcie Merge.

Pseudokód

Nech nech má funkcia MergeSort nasledovný prototyp: MergeSort(pole[], lavy, pravy)

1. Je lavy <= pravy ? Ak áno, skonči volanie, inak pokračuj krokom 2.

2. Nech: stred = floor((pravy - lavy) / 2)

2. Rekurzívne zavolaj funkciu MergeSort(pole[], lavy , stred)

3. Rekurzívne zavolaj funkciu MergeSort(pole[], stred + 1 , pravy)

4. Zavolaj funkciu Merge(pole[], lavy, stred, pravy)

5. Skonči volanie.