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 na vstupe prijmeme dva alebo viac utriedených zoznamov, ktoré skombinuje do jedného výstupného utriedeného zoznamu. Výstupný zoznam musí obsahovať všetky prvky z oboch vstupných 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 P index j.

Slovný opis algoritmu

Máme pole, ktoré sa skladá z dvoch už utriedených polovíc. Vytvoríme dve pomocné polia L a P, do ktorých skopírujeme 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 najmenšieho po najväčší). Tento prvok potom vložíme na prvú voľnú pozíciu vstupného poľa. Index vstupného poľa zvyšujeme vždy, keď doňho vložíme nejaký prvok a pri pomocnomých poliach zasa vtedy, keď z nich prvok vyberáme. 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 pridávame na koniec do vstupné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 (výmena smerníkov)
• využitie: 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 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 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

C

#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);
}

C++

#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);
}

Java

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);
    }
}

Python3

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 algoritmu Mergesortu

#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