streamalism.org

1. Úvod

V tejto príručke sa pozrieme na algoritmus Merge Sort a jeho implementácia v Jave.

Zlúčenie je jedna z najefektívnejších techník triedenia a je založená na paradigme „rozdeľuj a panuj“.

2. Algoritmus

Zlúčenie je algoritmus „rozdeľuj a panuj“, pri ktorom najskôr rozdelíme problém na podproblémy. Keď sú riešenia podproblémov pripravené, spojíme ich dohromady, aby sme dosiahli konečné riešenie problému.

Toto je jeden z algoritmov, ktorý je možné ľahko implementovať pomocou rekurzie, pretože sa zaoberáme čiastkovými problémami a nie hlavným problémom.

Algoritmus možno opísať ako nasledujúci 2 krokový proces:

• Rozdeliť: V tomto kroku rozdelíme vstupné pole na 2 polovice, pričom otočný bod je stredom poľa. Tento krok sa vykonáva rekurzívne pre všetky polovičné polia, kým už nie sú k dispozícii ďalšie polovičné polia na rozdelenie.
• Conquer: V tomto kroku triedime a zlúčime rozdelené polia zdola nahor a získate zoradené pole.

Nasledujúca schéma zobrazuje kompletný proces triedenia zlúčenia pre vzorové pole {10, 6, 8, 5, 7, 3, 4}.

Ak sa pozrieme bližšie na diagram, môžeme vidieť, že pole je rekurzívne rozdelené na dve polovice, až kým sa veľkosť nestane 1. Akonáhle sa veľkosť zmenší na 1, zlučovacie procesy vstúpia do činnosti a pri triedení začnú zlučovať polia späť:

3. Implementácia

Na implementáciu napíšeme a mergeSort funkcia, ktorá prijíma vstupné pole a jeho dĺžku ako parametre. Toto bude rekurzívna funkcia, takže potrebujeme základňu a rekurzívne podmienky.

Základná podmienka skontroluje, či je dĺžka poľa 1 a iba sa vráti. Vo zvyšných prípadoch sa uskutoční rekurzívne volanie.

Pre rekurzívny prípad získame stredný index a vytvoríme dve dočasné polia l [] a r []. The mergeSort funkcia sa potom volá rekurzívne pre obidva podradené polia:

public static void mergeSort (int [] a, int n) {if (n <2) {return; } int stred = n / 2; int [] l = nový int [stred]; int [] r = nový int [n - stred]; pre (int i = 0; i <mid; i ++) {l [i] = a [i]; } for (int i = mid; i <n; i ++) {r [i - mid] = a [i]; } mergeSort (l, stred); mergeSort (r, n - stred); zlúčiť (a, l, r, stred, n - stred); }

Potom voláme zlúčiť funkcia, ktorá zaberá vstupné a obidve čiastkové polia a začiatočný a koncový index oboch čiastkových polí.

The zlúčiť Funkcia porovnáva po jednom prvky obidvoch podradených polí a umiestňuje menší prvok do vstupného poľa.

Keď sa dostaneme na koniec jedného z podradených polí, zvyšok prvkov z druhého poľa sa skopíruje do vstupného poľa, čím sa získa konečné zoradené pole:

verejné statické neplatné zlúčenie (int [] a, int [] l, int [] r, int vľavo, int vpravo) {int i = 0, j = 0, k = 0; while (i <left && j <right) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } else {a [k ++] = r [j ++]; }} while (i <left) {a [k ++] = l [i ++]; } while (j <vpravo) {a [k ++] = r [j ++]; }} 

Jednotkový test programu:

@Test public void positiveTest () {int [] actual = {5, 1, 6, 2, 3, 4}; int [] očakávané = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (skutočná, skutočná.dĺžka); assertArrayEquals (očakávaný, skutočný); }

4. Zložitosť

Pretože zlúčenie je rekurzívny algoritmus, je možné časovú zložitosť vyjadriť ako nasledujúci rekurzívny vzťah:

T (n) = 2T (n / 2) + O (n)

2T (n / 2) zodpovedá času potrebnému na triedenie podradených polí a O (n) čas na zlúčenie celého poľa.

Po vyriešení časová zložitosť príde na O (nLogn).

Platí to pre najhorší, priemerný a najlepší prípad, pretože pole sa vždy rozdelí na dve a potom sa zlúči.

Priestorová zložitosť algoritmu je O (n) pretože pri každom rekurzívnom volaní vytvárame dočasné polia.

5. Záver

V tomto rýchlom výučbe sme videli fungovanie algoritmu zlučovania a toho, ako ho môžeme implementovať v Jave.

Celý pracovný kód je k dispozícii na GitHub.