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

Vlastnosti algoritmu

• 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)

Slovný opis algoritmu - treba refaktorovať

Pri zavolaní funkcie MergeSort, jej program pošle 3 údaje: pole, ktoré chceme zoradiť, index prvého prvku daného pola a index posledného prvku pola. Funkcia si vypočíta index prostredného prvku pola (pri nepárnom počte prvkov pola je to index prvku, ktorý sa vypočíta ako dĺžka_pola / 2, a táto hodnota je zaokrúhlená nadol) a podľa tohto prvku pole rozdelí na ľavú a pravú časť. Vo vnútri funkcie sa nachádzajú dve rekurzívne volania, a to pre ľavú časť pola a pre pravú časť pola. Tento cyklus sa opakuje dokým novovzniknuté polia nemajú práve 1 prvok. Akonáhle majú vzniknuté polia 1 prvok, tak sa ukončí rekurzívne volanie a nastupuje volanie funkcie Merge. Funkcia Merge bude vzniknuté polia postupne spájať dokopy, pričom prvky daných polí usporiada vzostupne. Výsledkom funkcie MergeSort je pole s uporiadanými prvkami.

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 + (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.

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