MergeSort

Z CHWiki

[editovat] Popis

Merge sort patrí k pokorčilejším triediacim algoritmom. Je to rekurzívny algoritmus a pracuje na princípe rozdeľ a panuj, jeho nevýhodou je potreba pomocného poľa. Merge sort rozdelí pole na polovice, každú túto polovicu rekurzívne spracuje (rozdelí aj tieto polovice na ďalšie polovice), a potom ich spojí, pričom ich nespojí tak, že jednoducho dá jednu za druhú, ale prvky z druhej polovice dá na správne miesto do prvej (samotné polovice sú utriedené, lebo algoritmus bol na ne rekurzívne volaný).

[editovat] Príklad

pole na pred triedením
  6 8 4 5 2 3 1 7 0 9

1. rozdelenie
  6 8 4 5 2  |  3 1 7 0 9
2. rozdelenie
  6 8  |  4 5 2  | 3 1  |  7 0 9
3. rozdelenie
  6  |  8  |  4  |  5 2  |  3  |  1  |  7  |  0 9
4. rozdelenie
  6  |  8  |  4  |  5  |  2  |  3  |  1  |  7  |  0  |  9

spájanie
  6  |  8  |  4  |  2 5  |  3  |  1  |  7  |  0 9	
  6 8  |  2 4 5  |  1 3  |  0 7 9  
  2 4 5 6 8  |  0 1 3 7 9  
  0 1 2 3 4 5 6 7 8 9

[editovat] Implementácia

function spoj(pole, lavy, pravy)
    tmp[pravy - lavy + 1]
    stred := (pravy + lavy) / 2
    koniecLavej := stred
    koniecPravej := pravy
    q := 1
    i := lavy
    j := stred + 1
    // kým sú v obidvoch poloviciach prvky
    while i <= koniecLavej and j <= koniecPravej
        // ak je prvý prvok (ešte nespracovaný) v prvej polovici
        // menší ako prvý takýto prvok v druhej, pridaj do pomocného 
        // poľa prvok z prvej, inak z druhej
        if pole[i] < pole[j]
            tmp[q] := pole[i]
            i := i + 1
        end if
        else
            tmp[q] := pole[j]
            j := 1 + 1
        end else
        q := q + 1
    end while
    // v jedenj z polovíc sa minuli prvky, prvky z polovice, 
    // v ktorej prvky ostali, pridá do pomocného poľa
    while i <= koniecLavej do
        tmp[q] := pole[i]
        q := q + 1
        i := i + 1
    end while

    while j <= koniecPravej do
        tmp[q] := pole[j]
        q := q + 1
        j := j + 1
    end while
    // utriedené prvky v pomocnom poli skopíruje naspäť 
    // do normálneho poľa
    for ii := lavy to pravy
        pole[ii] = tmp[ii - lavy + 1]
    end for
end function




function mergeSort(pole, lavy, pravy)
    if lavy < pravy
        stred := (lavy + pravy) / 2
        mergeSort(pole, lavy, stred)
        mergeSort(pole, stred+1, pravy)
        spoj(pole, lavy, pravy)
    end if
end function

Efektívnosť algoritmu je v značnej miere závislá na konkrétnej implementácií funkcie spoj, táto môže mať rôzne obmeny. Časová náročnosť algoritmu je O(n * log n), pamäťová je O(n) (existujú aj implementácie, ktoré nepotrebujú pomocné pole