streamalism.org

1. Uvod

U ovom uputstvu ćemo pogledati algoritam Merge Sort i njegova implementacija u Javi.

Sortiranje spajanjem jedna je od najučinkovitijih tehnika sortiranja i temelji se na paradigmi "podijeli i osvoji".

2. Algoritam

Spajanje sortiranja algoritam je "podijeli i osvoji" u kojem problem prvo dijelimo na podprobleme. Kada su rješenja za potprobleme spremna, kombiniramo ih zajedno kako bismo dobili konačno rješenje problema.

Ovo je jedan od algoritama koji se lako može implementirati pomoću rekurzije jer se bavimo potproblemima, a ne glavnim problemom.

Algoritam se može opisati kao sljedeći postupak u dva koraka:

• Podijeli: U ovom koraku ulazni niz dijelimo na 2 polovice, stožer je središnja točka niza. Ovaj se korak izvodi rekurzivno za sve polovice nizova sve dok više nema pola nizova za dijeljenje.
• Conquer: U ovom koraku sortiramo i spajamo podijeljene nizove odozdo prema gore i dobiti sortirani niz.

Sljedeći dijagram prikazuje kompletan postupak sortiranja spajanja za primjer niza {10, 6, 8, 5, 7, 3, 4}.

Ako pažljivije pogledamo dijagram, možemo vidjeti da se niz rekurzivno dijeli na dvije polovice sve dok veličina ne postane 1. Kad veličina postane 1, postupci spajanja započinju s akcijom i započinju spajanje nizova natrag tijekom sortiranja:

3. Provedba

Za provedbu, napisat ćemo a mergeSort funkcija koja uzima ulazni niz i njegovu duljinu kao parametri. Ovo će biti rekurzivna funkcija pa nam trebaju baza i rekurzivni uvjeti.

Osnovni uvjet provjerava je li duljina polja 1 i on će se samo vratiti. U ostalim će se slučajevima izvršiti rekurzivni poziv.

Za rekurzivni slučaj dobivamo srednji indeks i stvaramo dva privremena niza l [] i r []. The mergeSort funkcija se tada rekurzivno poziva za oba podniza:

javna statička void mergeSort (int [] a, int n) {if (n <2) {return; } int sredina = n / 2; int [] l = novo int [sredina]; int [] r = novo int [n - sredina]; za (int i = 0; i <mid; i ++) {l [i] = a [i]; } za (int i = sredina; i <n; i ++) {r [i - sredina] = a [i]; } mergeSort (l, sredina); mergeSort (r, n - sredina); spajanje (a, l, r, sredina, n - sredina); }

Zatim zovemo sjediniti funkcija koja uzima ulaz i pod-nizove te početni i krajnji indeks oba pod-niza.

The sjediniti funkcija uspoređuje elemente oba podniza jedan po jedan i smješta manji element u ulazni niz.

Kad dođemo do kraja jednog od pod-nizova, ostatak elemenata iz drugog niza kopira se u ulazni niz, čime dobivamo konačni sortirani niz:

javno statično spajanje praznina (int [] a, int [] l, int [] r, int lijevo, int desno) {int i = 0, j = 0, k = 0; dok (i <lijevo && j <desno) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } else {a [k ++] = r [j ++]; }} while (i <lijevo) {a [k ++] = l [i ++]; } while (j <desno) {a [k ++] = r [j ++]; }} 

Jedinstveni test za program:

@Test public void positiveTest () {int [] stvarna = {5, 1, 6, 2, 3, 4}; int [] očekuje se = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (stvarna, stvarna.duljina); assertArrayEquals (očekivano, stvarno); }

4. Složenost

Kako je sortiranje stapanja rekurzivni algoritam, vremenska složenost može se izraziti kao sljedeća rekurzivna relacija:

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

2T (n / 2) odgovara vremenu potrebnom za razvrstavanje podsredova i Na) vrijeme za spajanje cijelog niza.

Kada se riješi, doći će vrijeme složenosti O (nLogn).

To vrijedi za najgori, prosjek i najbolji slučaj, jer će uvijek podijeliti niz na dva i zatim spojiti.

Složenost prostora algoritma je Na) jer stvaramo privremene nizove u svakom rekurzivnom pozivu.

5. Zaključak

U ovom smo brzom vodiču vidjeli kako funkcionira algoritam sortiranja spajanja i kako ga možemo implementirati u Javi.

Cijeli radni kod dostupan je na GitHubu.