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

2. Nech: dlzka_L = stred - lavy + 1, dlzka_P = pravy - stred

3. Nech: L = pole[lavy ... stred], P = pole[stred + 1 ... pravy]

4. Je i < dlzka_L a zároveň j < dlzka_P ? Ak áno, pokračuj krokom 3.1., inak skok na krok 5.

4.1. Je L[i] <= P[j]? Ak áno, pole[k++] = L[i++], inak pole[k++] = P[j++].

4.2. Skok na krok 4.

5. Je i < dlzka_L ? Ak áno, pokračuj krokom 4.1., inak skok na krok 6.

5.1. pole[k++] = L[i++]

5.2. Skok na krok 5.

6. Je j < dlzka_P ? Ak áno, pokračuj krokom 5.1., inak skonči program.

6.1. pole[k++] = P[j++]

6.2. Skok na krok 6.

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 = lavy + floor((pravy - lavy) / 2)

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

Implementácia v jazyku C

  1 void Merge(int pole[], int lavy, int stred, int pravy);
  2 void MergeSort(int pole[], int lavy, int pravy);
  3 
  4 /* hlavný program */
  5 
  6 int main()
  7 {
  8     int pole[] = {12, 11, 13, 5, 6, 7};
  9     int dlzka_pola = sizeof(pole) / sizeof(pole[0]);
 10 
 11     printf("Pôvodné pole: \n");
 12 
 13     for (int i = 0; i < dlzka_pola; ++i)
 14     {
 15         printf("%d ", pole[i]);
 16     }
 17 
 18     MergeSort(pole, 0, dlzka_pola - 1);
 19 
 20     printf("\nUtriedené pole: \n");
 21 
 22     for (int i = 0; i < dlzka_pola; ++i)
 23     {
 24         printf("%d ", pole[i]);
 25     }
 26     
 27     return 0;
 28 }
 29 
 30 void Merge(int pole[], int lavy, int stred, int pravy)
 31 {
 32    /* ak má pole menej ako 2 prvky, skonči */
 33 
 34     if (lavy >= pravy)
 35     {
 36         return;
 37     }
 38 
 39    /* vyrátaj dĺžky oboch polovíc poľa */
 40 
 41    int L_dlzka = stred - lavy + 1;
 42    int P_dlzka = pravy - stred;
 43 
 44    /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */
 45 
 46    int *L = (int*)malloc(L_dlzka * sizeof(int));
 47    int *P = (int*)malloc(P_dlzka * sizeof(int));
 48 
 49    /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */
 50 
 51    int i, j, k;
 52 
 53    /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */
 54 
 55    for (i = 0; i < L_dlzka; ++i)
 56    {
 57        L[i] = pole[lavy + i];
 58    }
 59 
 60    for (j = 0; j < P_dlzka; ++j)
 61    {
 62        P[j] = pole[stred + 1 + j];
 63    }
 64 
 65    /* nastav indexy na začiatok daných polí */
 66 
 67    i = 0; j = 0; k = lavy;
 68 
 69   /* zlučuj dočasné polia L a P do finálneho poľa pole */
 70 
 71    while(i < L_dlzka && j < P_dlzka)
 72    {
 73        if(L[i] <= P[j])
 74        {
 75            pole[k++] = L[i++];
 76        }
 77        else
 78        {
 79            pole[k++] = P[j++];
 80        }
 81    }
 82 
 83    /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */
 84 
 85    while(i < L_dlzka)
 86    {
 87        pole[k++] = L[i++];
 88    }
 89 
 90    /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */
 91 
 92    while(j < P_dlzka)
 93    {
 94        pole[k++] = P[j++];
 95    }
 96 
 97    /* uvoľni použitú pamäť */
 98 
 99    free(L);
100    free(P);
101 }
102 
103 void MergeSort(int pole[], int lavy, int pravy)
104 {
105     /* ak má pole menej ako 2 prvky, skonči volanie */
106 
107     if(lavy >= pravy)
108     {
109         return;
110     }
111     /* urči si prostredný index */
112 
113     int stred = lavy + (pravy - lavy) / 2;
114 
115     /* utrieď ľavú polovicu poľa */
116 
117     MergeSort(pole, lavy, stred);
118 
119     /* utrieď pravú polovicu poľa */
120 
121     MergeSort(pole, stred+1, pravy);
122 
123     /* zlúč obe polovice dokopy */
124 
125     Merge(pole, lavy, stred, pravy);
126 }