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čovací algoritmus Merge

Princíp zlučovania tkvie v tom, že máme dva alebo viac utriedených zoznamov, ktoré skombinuje do jedného utriedeného zoznamu (výsledný zoznam musí obsahovať všetky prvky z pôvodných dvoch zoznamov). 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.

Algoritmus Merge tvorí dôležitú časť triediaceho algoritmu MergeSort.

Vizualizácia funkcie Merge: Máme pole prvkov p = [1, 3, 5, 2, 4, 6], ktoré je už čiastočne utriedené. Použijeme algoritmus Merge, ktorý si vytvorí pomocné polia L = [1, 3, 5] a P = [2, 4, 6]. Všetky polia indexujeme od 0, pričom pre pole p používame index k, pre L index i a pre P index j. Postupnosť krokov je označená číslicami 1 až 6.

Slovný opis algoritmu

Máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme si dve pomocné polia L a P, do ktorých skopírujeme obsahy oboch týchto polovíc. Potom súčasne prechádzame polia L a P od začiatku po koniec a v každom cykle porovnáme prvok poľa L s prvkom v poľa P. Z tejto dvojice následne vyberieme minimum, (keď triedime od najmenšieho po najväčší) ktoré vložíme na prvú voľnú pozíciu pôvodného poľa (na začiatku je to prvý index tohto poľa). Nakoniec zvýšime index pri vstupnom poli a pri poli z ktorého vyberáme daný prvok. Túto postupnosť cyklicky opakujeme, pokiaľ neprídeme na koniec jedného z polí P a L. Ak nastane situácia, že prídeme na koniec len jedného z pomocných polí , a v druhom nám ostali ešte nevybrané prvky, potom už iba naspäť skopírujeme zbytok tohto poľa do pôvodného poľa.

Vlastnosti algoritmu

• vhodný pre dátové štruktúry: pole, lineárny zoznam
• časová náročnosť: vždy lineárna [math] O(n) [/math]
• priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie dočasných polí), [math]O(1)[/math] pre lineárny zoznam (pri LZ netreba alokovať dočasné polia, satčí iba vymeniť smerníky)
• využitie: kľúčový podprogram pre triediaci algoritmus MergeSort

Pseudokód

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

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

2. Nech: i = 0, j = 0, k = lavy

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

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

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

5.1. Je L[i] <= P[j]?

Ak áno:

5.1.1.pole[k] = L[i]

5.1.2k += 1

5.1.3i += 1

5.1.4 skoč na krok 5.

Ak nie:

5.1.1.pole[k] = P[j]

5.1.2.k += 1

5.1.3.j += 1

5.1.4. skoč na krok 5.

6. Je i < dlzka_L ? Ak áno, pokračuj krokom 6.1., inak skoč na krok 7.

6.1. pole[k] = L[i]

6.2.k += 1

6.3.i += 1

6.4. Skoč na krok 6.

7. Je j < dlzka_P ? Ak áno, pokračuj krokom 7.1., inak skonči.

7.1. pole[k] = P[j]

7.2.k += 1

7.3.j += 1

7.4. Skok na krok 7.

Merge sort

Vizualizácia algoritmu MergeSort

Merge Sort je triediaci algoritmus, ktorý je založený na stratégii "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é triediace algoritmy.

Z hľadiska implementácie môžeme vytvoriť dve základné verzie algoritmu, a to rekurzívnu a iteračnú.

Princíp rekurzívneho algoritmu

Algoritmus MergeSort vykonáva 4 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.

Slovný opis rekurzívneho algoritmu

Máme pole, ktoré máme utriediť (zvolili sme vzostupné triedenie: min - max). Určíme si stred poľa (pri párnom počte prvkov je to ten menší prostredný index). Následne vykonávame sériu rekurzívnych delení pre ľavú a pravú časť poľa (začiatok - stred, stred + 1, koniec) až do momentu, keď nám ostane len jednoprvkové pole (to je už utriedené). Následne v každom volaní obe časti zlúčime pomocou algoritmu Merge.

Súbor:MergeSort It.png

400px

Princíp iteračného algoritmu

Algoritmus Merge vykonáva 3 základné úlohy:

1. Vonkajší cyklus: určenie veľkosti zoznamu na zlučovanie
2. Vnútorný cyklus: prechádzanie jednotlivých zoznamov v poli
3. Zlučovanie jednotlivých zoznamov pomocou funkcie Merge

Slovný opis iteračného algoritmu

Naše vstupné pole, ktoré má n prvkov, predstavuje n rôznych jednoprvkových (utriedených) zoznamov, ktoré máme zlúčiť do jedného n-prvkového utriedeného zoznamu. Keďže by bolo veľmi nepraktické zlučovať n-zoznamov naraz zvolíme nasledovnú stratégiu. Budeme prechádzať dané pole od začiatku po koniec a v prvom cykle zlúčime každé dva prvky, takže budeme mať n/2 dvojprvkových utiredených zoznamov. Tento princíp môžeme opakovať, čiže v druhom cykle zlúčime každé 4 prvky do jedného zoznamu, v treťom cykle, každých 8, až do momentu, keď dostaneme jeden utriedený zoznam. Aby sme to docielili, potrebujeme dva cykly, vonkajší, ktorý nastaví veľkosť zoznamov, ktoré ideme zlučovať (1,2,4,8 ... dlzka - 1) a vnútorný, ktorý prechádza dané zoznamy. Následne už iba voláme funkciu Merge, ktorá dané zoznamy zlučuje.

Poznámka, ak máme pole, ktoré má nepárny počet prvkov, tak ten posledný nezlúčime v prvom prvom kroku, ale až v ďalších. Takisto, ak n nie je mocnina 2, tak musíme ošetriť mimo pole ...

Vlastnosti algoritmu MergeSort

• vhodný pre dátové štruktúry: pole, lineárny zoznam
• časová náročnosť: vždy linearitmická [math] O(n.log(n)) [/math]
• priestorová náročnosť: lineárna [math]O(n)[/math] pre pole (alokovanie dočasných polí), konštantná [math]O(1)[/math] pre lineárny zoznam (výmena smerníkov)
• druh triedenia: triedenie zlučovaním (komparačný algoritmus)
• stabilita triedenia: stabilný
• miesto triedenia: externé triedenie (vhodný na triedenie veľkých objemov dát uložených na disku)

Pseudokód pre rekurzívnu verziu

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 + (pravy - lavy) / 2, pričom znak / vyjadruje celočíselné delenie.

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.

Pseudokód pre iteračnú verziu

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

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

2. Nech: dlzka_subzoznamu = 1

3. Nech: zaciatok = lavy

4. Jedlzka_subzoznamu <= pravy ? Ak áno pokračuj krokom 4.1, inak skonči.

4.1. Jezaciatok < pravy Ak áno pokračuj krokom 4.1.1, inak skoč na krok 4.2.

4.1.1. Je zaciatok + 2 * dlzka_zoznamu - 1 <= pravy ?

Ak áno:

4.1.1.1. Nech koniec = zaciatok + 2 * dlzka_zoznamu - 1

Ak nie:

4.1.1.1. Nech koniec = pravy

4.1.2. Je zaciatok + dlzka_zoznamu - 1 <= pravy ?

Ak áno:

4.1.2.1. Nech stred = zaciatok + dlzka_zoznamu - 1

Ak nie:

4.1.2.1. Nech stred = pravy

4.1.3. Merge(pole[], zaciatok, stred, koniec)

4.1.4. zaciatok += 2 * dlzka_subzoznamu

4.1.5. Skoč na krok 4.1.

4.2. dlzka_subzoznamu *= 2

4.3 Skoč na krok 4.

Implementácia algoritmov Merge a MergeSort

Rekurzívna verzia algoritmov

CC++JavaPython3

#include <stdio.h>
#include <stdlib.h>



void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSort(int pole[], int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    MergeSort(pole, 0, dlzka_pola - 1);

    printf("\nUtriedené pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }
    
    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
   /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

   /* vyrátaj dĺžky oboch polovíc poľa */

   int L_dlzka = stred - lavy + 1;
   int P_dlzka = pravy - stred;

   /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

   int *L = (int*)malloc(L_dlzka * sizeof(int));
   int *P = (int*)malloc(P_dlzka * sizeof(int));

   /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

   int i, j, k;

   /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

   for (i = 0; i < L_dlzka; ++i)
   {
       L[i] = pole[lavy + i];
   }

   for (j = 0; j < P_dlzka; ++j)
   {
       P[j] = pole[stred + 1 + j];
   }

   /* nastav indexy na začiatok daných polí */

   i = 0; j = 0; k = lavy;

  /* zlučuj dočasné polia L a P do finálneho poľa pole */

   while(i < L_dlzka && j < P_dlzka)
   {
       if(L[i] <= P[j])
       {
           pole[k++] = L[i++];
       }
       else
       {
           pole[k++] = P[j++];
       }
   }

   /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

   while(i < L_dlzka)
   {
       pole[k++] = L[i++];
   }

   /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

   while(j < P_dlzka)
   {
       pole[k++] = P[j++];
   }

   /* uvoľni použitú pamäť */

   free(L);
   free(P);
}

void MergeSort(int pole[], int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }
    /* urči si prostredný index */

    int stred = lavy + (pravy - lavy) / 2;

    /* utrieď ľavú polovicu poľa */

    MergeSort(pole, lavy, stred);

    /* utrieď pravú polovicu poľa */

    MergeSort(pole, stred+1, pravy);

    /* zlúč obe polovice dokopy */

    Merge(pole, lavy, stred, pravy);
}

#include <iostream>

using std::cout;
using std::endl;

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSort(int pole[], int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole: \n");

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    MergeSort(pole, 0, dlzka_pola - 1);

    cout<<endl<<"Utriedené pole:"<<endl;

    for (auto i: pole)
    {
        cout<<i<<" ";
    }

    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
   /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

   /* vyrátaj dĺžky oboch polovíc poľa */

   int L_dlzka = stred - lavy + 1;
   int P_dlzka = pravy - stred;

   /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

   int *L = new int[L_dlzka];
   int *P = new int[P_dlzka];

   /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

   int i, j, k;

   /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

   for (i = 0; i < L_dlzka; ++i)
   {
       L[i] = pole[lavy + i];
   }

   for (j = 0; j < P_dlzka; ++j)
   {
       P[j] = pole[stred + 1 + j];
   }

   /* nastav indexy na začiatok daných polí */

   i = 0; j = 0; k = lavy;

  /* zlučuj dočasné polia L a P do finálneho poľa pole */

   while(i < L_dlzka && j < P_dlzka)
   {
       if(L[i] <= P[j])
       {
           pole[k++] = L[i++];
       }
       else
       {
           pole[k++] = P[j++];
       }
   }

   /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

   while(i < L_dlzka)
   {
       pole[k++] = L[i++];
   }

   /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

   while(j < P_dlzka)
   {
       pole[k++] = P[j++];
   }

   /* uvoľni použitú pamäť */

   delete []L;
   delete []P;
}

void MergeSort(int pole[], int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }
    /* urči si prostredný index */

    int stred = lavy + (pravy - lavy) / 2;

    /* utrieď ľavú polovicu poľa */

    MergeSort(pole, lavy, stred);

    /* utrieď pravú polovicu poľa */

    MergeSort(pole, stred+1, pravy);

    /* zlúč obe polovice dokopy */

    Merge(pole, lavy, stred, pravy);
}

class MergeSort {
    /* Zlúči 2 subpolia, ktoré sa vytvorili z pôvodného pola.
    * Každé subpole má polovičnú dĺžku pôvodného pola.
    * subpole1 [ľavý..stred]
    * subpole2 [stred+1..pravý] */
    void merge(int[] pole, int lavy, int stred, int pravy) {
        // Výpočet dĺžky 2 subpolí
        int n1 = stred - lavy + 1;
        int n2 = pravy - stred;

        // Vytvorenie pomocných polí
        int[] L = new int[n1];
        int[] P = new int[n2];

        // Načítanie dát do pomocných polí
        for (int i = 0; i < n1; i++)
            L[i] = pole[lavy + i];

        for (int j = 0; j < n2; j++)
            P[j] = pole[stred + 1 + j];

        // Počiatočné indexy prvého a druhého subpola
        int i = 0, j = 0;
        // Počiatočný index zlúčeného subpola
        int k = lavy;

        // Zlúčenie dvoch podpolí
        while (i < n1 && j < n2) {
            if (L[i] <= P[j]) {
                pole[k] = L[i];
                i++;
            }
            else {
                pole[k] = P[j];
                j++;
            }
            k++;
        }

        /* V prípade, že v jednom zo subpolí sa nachádzajú prvky, ktoré neboli zlúčené do pola,
        * tak sa do pola jednoducho skopírujú */
        while (i < n1) {
            pole[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            pole[k] = P[j];
            k++;
            j++;
        }
    }

    /* Funkcia, ktorá zoradí pole použitím funkcie merge() */
    void sort (int[] pole, int lavy, int pravy) {
        if (lavy < pravy) {
            //Musíme nájsť stred pola
            int stred = lavy + (pravy - lavy) / 2;

            // Zoradíme prvú a druhú polovicu pola samostatne
            sort(pole, lavy, stred);
            sort(pole, stred + 1, pravy);

            // Zlúčime zoradené polovice do jedného pola
            merge(pole, lavy, stred, pravy);
        }
    }
}

public class Main {
    /* Funkcia na výpis pola dĺžky n */
    static void vypis_pole(int[] pole) {
        int n = pole.length;

        for (int i = 0; i < n; i++) {
            System.out.print(pole[i] + " ");
        }
        System.out.println();
    }
    
    /* Hlavný program */
    public static void main(String[] args) {
	    int[] pole = {12, 11, 13, 5, 6, 7};

        System.out.println("Zadané pole:");
        vypis_pole(pole);

        MergeSort ms = new MergeSort();
        ms.sort(pole, 0, pole.length - 1);

        System.out.println("\nZoradené pole:");
        vypis_pole(pole);
    }
}

def MergeSort(pole):
    if len(pole) > 1:
        # Nájdenie stredu pola
        # zápis len(pole)//2 znamená, že dĺžka pola sa vydelí 2 a výsledok je celé číslo
        stred = len(pole) // 2

        # Rozdelenie pola na dve časti
        L = pole[:stred]
        P = pole[stred:]

        # Zoradenie najskôr prvej časti pola, potom druhej
        MergeSort(L)
        MergeSort(P)

        i = j = k = 0

        # Načítanie dát do pomocných polí L[] a P[]
        while i < len(L) and j < len(P):
            if L[i] < P[j]:
                pole[k] = L[i]
                i += 1
            else:
                pole[k] = P[j]
                j += 1
            k += 1

        # Kontrola či všetky prvky boli zlúčené dokopy,
        # ak nie, tak sa do zlúčeného pola jednoducho skopírujú
        while i < len(L):
            pole[k] = L[i]
            i += 1
            k += 1

        while j < len(P):
            pole[k] = P[j]
            j += 1
            k += 1


# Kód na výpis pola
def vypis_pole(pole):
    for i in range(len(pole)):
        print(pole[i], end=" ")
    print()


# Hlavný program
if __name__ == '__main__':
    pole = [12, 11, 13, 5, 6, 7]
    print("Zadané pole:", end="\n")
    vypis_pole(pole)
    MergeSort(pole)
    print("Zoradené pole:", end="\n")
    vypis_pole(pole)

Iteračná verzia algoritmov

C

#include <stdio.h>
#include <stdlib.h>

void Merge(int pole[], int lavy, int stred, int pravy);
void MergeSortIt(int *pole, int lavy, int pravy);

/* hlavný program */

int main()
{
    int pole[] = {12, 11, 13, 5, 6, 7, 19};
    int dlzka_pola = sizeof(pole) / sizeof(pole[0]);

    printf("Pôvodné pole %d: \n", dlzka_pola);

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    MergeSortIt(pole, 0, dlzka_pola - 1);

    printf("\nUtriedené pole: \n");

    for (int i = 0; i < dlzka_pola; ++i)
    {
        printf("%d ", pole[i]);
    }

    return 0;
}

void Merge(int pole[], int lavy, int stred, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči */

    if (lavy >= pravy)
    {
        return;
    }

    /* vyrátaj dĺžky oboch polovíc poľa */

    int L_dlzka = stred - lavy + 1;
    int P_dlzka = pravy - stred;

    /* alokuj dočasné polia, kam uložíš prvky z oboch polovíc poľa */

    int *L = (int*)malloc(L_dlzka * sizeof(int));
    int *P = (int*)malloc(P_dlzka * sizeof(int));

    /* indexy, ktorými iterujeme všetky polia: i pre L, j pre P, k pre pole */

    int i, j, k;

    /* skopíruj obsah oboch polovíc poľa do dočasných polí L a P */

    for (i = 0; i < L_dlzka; ++i)
    {
        L[i] = pole[lavy + i];
    }

    for (j = 0; j < P_dlzka; ++j)
    {
        P[j] = pole[stred + 1 + j];
    }

    /* nastav indexy na začiatok daných polí */

    i = 0; j = 0; k = lavy;

    /* zlučuj dočasné polia L a P do finálneho poľa pole */

    while(i < L_dlzka && j < P_dlzka)
    {
        if(L[i] <= P[j])
        {
            pole[k++] = L[i++];
        }
        else
        {
            pole[k++] = P[j++];
        }
    }

    /* ak ostali nejaké prvky v dočasnom poli L, skopíruj ich do finálneho poľa */

    while(i < L_dlzka)
    {
        pole[k++] = L[i++];
    }

    /* ak ostali nejaké prvky v dočasnom poli P, skopíruj ich do finálneho poľa */

    while(j < P_dlzka)
    {
        pole[k++] = P[j++];
    }

    /* uvoľni použitú pamäť */

    free(L);
    free(P);
}

void MergeSortIt(int *pole, int lavy, int pravy)
{
    /* ak má pole menej ako 2 prvky, skonči volanie */

    if(lavy >= pravy)
    {
        return;
    }

    int stred, koniec;

    for (int dlzka_zoznamu = 1; dlzka_zoznamu <= pravy ; dlzka_zoznamu *= 2)
    {
        for (int zaciatok = lavy; zaciatok < pravy ; zaciatok += 2 * dlzka_zoznamu)
        {
             koniec = (zaciatok + 2 * dlzka_zoznamu - 1 <= pravy) ? zaciatok + 2 * dlzka_zoznamu - 1 : pravy;

             stred = (zaciatok + dlzka_zoznamu - 1 <= pravy) ? zaciatok + dlzka_zoznamu - 1 : pravy;

             Merge(pole, zaciatok, stred, koniec);

        }
    }
}

Odkazy

1. https://www.geeksforgeeks.org/merge-sort/
2. https://medium.com/@paulsoham/merge-sort-63d75df76388
3. https://www.khanacademy.org/computing/computer-science/algorithms/merge-sort/a/overview-of-merge-sort
4. https://www.tutorialspoint.com/data_structures_algorithms/merge_sort_algorithm.htm