Merge sort je eden od osnovnih algoritmov računalništva, ki ga je leta 1945 oblikoval veliki matematik John von Neumann. Med sodelovanjem v projektu Manhattan se je Neumann soočil s potrebo po učinkoviti obdelavi ogromnih količin podatkov. Metoda, ki jo je razvil, je uporabljala načelo "deli in obvladuj", kar je znatno zmanjšalo čas, potreben za delo.
Načelo in uporaba algoritma
Metoda razvrščanja z združitvijo se uporablja pri težavah pri razvrščanju struktur, ki imajo urejen dostop do elementov, kot so nizi, seznami, tokovi.
Med obdelavo se začetni podatkovni blok razdeli na majhne komponente, do enega elementa, ki je pravzaprav že razvrščen seznam. Nato se ponovno sestavi v pravilnem vrstnem redu.
Razvrščanje matrike določene dolžine zahteva dodatno pomnilniško območje enake velikosti, v katerem je razvrščeni niz zbran po delih.
Metodo lahko uporabite za naročanje katere koli primerljive vrste podatkov, kot so številke ali nizi.
Spoji razvrščenoparcele
Da bi razumeli algoritem, začnimo njegovo analizo od konca - od mehanizma združevanja razvrščenih blokov.
Predstavljajmo si, da imamo dva niza številk, razvrščenih na kakršen koli način, ki jih je treba med seboj kombinirati, da se razvrščanje ne prekine. Zaradi preprostosti bomo številke razvrstili v naraščajočem vrstnem redu.
Elementarni primer: obe matriki sta sestavljeni iz enega elementa.
int arr1={31}; int arr2={18};
Če želite ju združiti, morate vzeti ničelni element prve matrike (ne pozabite, da se številčenje začne od nič) in ničelni element drugega niza. To sta 31 oziroma 18. Glede na pogoj razvrščanja bi morala biti številka 18 prva, saj je manjša. Samo postavite številke v pravilnem vrstnem redu:
int rezultat={18, 31};
Oglejmo si bolj zapleten primer, kjer je vsak niz sestavljen iz več elementov:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritem spajanja bo sestavljen iz zaporedne primerjave manjših elementov in njihovega umestitve v nastalo matriko v pravilnem vrstnem redu. Za spremljanje trenutnih indeksov uvedemo dve spremenljivki - index1 in index2. Na začetku jih nastavimo na nič, saj so nizi razvrščeni, najmanjši elementi pa so na začetku.
int index1=0; int indeks2=0;
Napišimo celoten postopek združevanja korak za korakom:
- Vzemite element z indeksom1 iz matrike arr1 in element z indeksom2 iz matrike arr2.
- Primerjaj, izberi najmanjšega in vstavinastala matrika.
- Povečaj trenutni indeks manjšega elementa za 1.
- Nadaljujte od prvega koraka.
Na prvi orbiti bo situacija videti takole:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; rezultat[0]=arr1[0]; // rezultat=[2]
Na drugem zavoju:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; rezultat[1]=arr2[0]; // rezultat=[2, 5]
tretji:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; rezultat[2]=arr2[1]; // rezultat=[2, 5, 6]
In tako naprej, dokler rezultat ni popolnoma razvrščen niz: {2, 5, 6, 17, 21, 19, 30, 45}.
Če združite nize različnih dolžin, lahko nastanejo določene težave. Kaj pa, če je eden od trenutnih indeksov dosegel zadnji element in so v drugem nizu še vedno ostali člani?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 korak index1=0, index2=0; 1 2 rezultat={1, 2}; // 3 korak index1=1, index2=1; 4 < 5 rezultat={1, 2, 4}; //4 korak index1=2, index2=1 ??
Spremenljivka index1 je dosegla vrednost 2, vendar matrika arr1 nima elementa s tem indeksom. Tukaj je vse preprosto: samo prenesite preostale elemente drugega niza v nastalo, pri čemer ohranite njihov vrstni red.
rezultat={1, 2, 4, 5, 6, 7, 9};
Ta situacija nam kaže na potreboprimerjaj trenutni kontrolni indeks z dolžino matrike, ki se spaja.
Shema spajanja za urejena zaporedja (A in B) različnih dolžin:
- Če je dolžina obeh zaporedij večja od 0, primerjajte A[0] in B[0] in premaknite manjšega v medpomnilnik.
- Če je dolžina enega od zaporedij 0, vzemite preostale elemente drugega zaporedja in se, ne da bi spremenili njihov vrstni red, premaknite na konec medpomnilnika.
Izvedba druge faze
Primer združevanja dveh razvrščenih nizov v Javi je podan spodaj.
int a1=novo int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=novo int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=novo int[a1.length + a2.length]; int i=0, j=0; za (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } sicer if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } sicer če (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } drugače { int b=a2[j]; a3[k]=b; j++; } }
Tukaj:
- a1 in a2 sta izvirna razvrščena matrika, ki ju je treba združiti;
- a3 – končni niz;
- i in j sta indeksa trenutnih elementov za matrike a1 in a2.
Prvi in drugi, če pogoji zagotavljajo, da indeksi ne presegajo velikosti matrike. Tretji oziroma četrti pogojni blok se premakneta v nastalo matriko manjšega elementa.
razdeli in vladaj
Torej smo se naučili združiti razvrščenozbirke vrednot. Lahko rečemo, da je bil drugi del algoritma razvrščanja z združitvijo - samo spajanje - že razvrščen.
Vendar pa morate še vedno razumeti, kako priti iz prvotnega nerazvrščenega niza številk na več razvrščenih, ki jih je mogoče združiti.
Razmislimo o prvi stopnji algoritma in se naučimo ločiti matrike.
To ni težko - prvotni seznam vrednosti je razdeljen na polovico, nato se vsak del tudi razcepi in tako naprej, dokler ne dobimo zelo majhnih blokov.
Dolžina takšnih minimalnih elementov je lahko enaka eni, to pomeni, da so lahko sami razvrščeni niz, vendar to ni nujen pogoj. Velikost bloka je določena vnaprej in za njegovo naročanje lahko uporabite kateri koli ustrezen algoritem razvrščanja, ki učinkovito deluje z nizi majhnih velikosti (na primer hitro razvrščanje ali razvrščanje z vstavljanjem).
Izgleda takole.
// originalni niz {34, 95, 10, 2, 102, 70}; // prvi deli {34, 95, 10} in {2, 102, 70}; // drugi delitev {34} in {95, 10} in {2} in {102, 70}
Nastale bloke, sestavljene iz 1-2 elementov, je zelo enostavno razporediti.
Po tem morate že razvrščene majhne nize združiti v pare, pri čemer ohranite vrstni red članov, kar smo se že naučili.
Izvedba prve faze
Rekurzivno particioniranje matrike je prikazano spodaj.
void mergeSort(T a, dolg začetek, dolg konec) { long split; če(začetek < cilj) { split=(start + cilj)/2; mergeSort(a, začetek, razdelitev); razvrsti z združitvijo (a, razdeli+1, konča); združi (a, začetek, razdelitev, konec); } }
Kaj se zgodi v tej kodi:
-
Funkcija mergeSort dobi začetno matriko
a
ter levo in desno mejo regije, ki jo je treba razvrstiti (indeksi začetek in
- konec).
-
Če je dolžina tega odseka večja od enega (
začetek < konec
), se razdeli na dva dela (z indeksom
- split), in vsak je rekurzivno razvrščen.
-
Pri klicu rekurzivne funkcije za levo stran se posreduje začetni indeks grafa in indeks
split
. Za desno bo začetek
- (split + 1), konec pa zadnji indeks prvotnega razdelka.
-
Funkcija
združi
dobi dve urejeni zaporedji (
a[začetek]…a[split]
in
- a[razdelitev +1]…a[dokončaj) in jih združi v vrstnem redu.
Mehanika funkcije spajanja je obravnavana zgoraj.
Splošna shema algoritma
Metoda matrike razvrščanja z združitvijo je sestavljena iz dveh velikih korakov:
- Razdelite nerazvrščeni izvirni niz na majhne koščke.
- Zberite jih v parih v skladu s pravilom razvrščanja.
Velika in zapletena naloga je razdeljena na veliko preprostih, ki se zaporedno rešujejo, kar vodi do želenega rezultata.
Ovrednotenje metode
Časovna zapletenost razvrščanja spajanja je določena z višino razdeljenega drevesaalgoritem in je enak številu elementov v nizu (n), pomnoženem z njegovim logaritemom (log n). Takšna ocena se imenuje logaritemska.
To je prednost in slabost metode. Njegov čas delovanja se ne spremeni niti v najslabšem primeru, ko je prvotni niz razvrščen v obratnem vrstnem redu. Vendar pri obdelavi popolnoma razvrščenih podatkov algoritem ne zagotavlja časovnega dobička.
Pomembno je tudi upoštevati stroške pomnilnika pri metodi razvrščanja z združitvijo. So enaki velikosti originalne zbirke. V tem dodatno dodeljenem območju je razvrščen niz sestavljen iz kosov.
Izvedba algoritma
Pascal razvrščanje spajanja je prikazano spodaj.
Postopek MergeSort(ime: niz; var f: besedilo); Var a1, a2, s, i, j, kol, tmp: celo število; f1, f2: besedilo; b: boolean Begincol:=0; Dodeli (f, ime); ponastavi (f); Čeprav ni EOF(f), začnite brati(f, a1); inc (stol.); konec; zapreti (f); Assign(f1, '{ime 1. pomožne datoteke}'); Assign(f2, '{ime 2. pomožne datoteke}'); s:=1; Medtem ko (s<kol) začne Reset(f); ponovno zapiši (f1); ponovno zapiši (f2); Za i:=1 do kol div 2 začnite Read(f, a1); Zapiši (f1, a1, ' '); konec; Če (kol div 2) mod s0, potem začnite tmp:=kol div 2; Medtem ko tmp mod s0 začne z branjem (f, a1); Zapiši (f1, a1, ' '); inc(tmp); konec; konec; Čeprav ni EOF(f), začnite Read(f, a2); Zapiši (f2, a2, ' '); konec; zapreti (f); zapri (f1); zapri (f2); prepiši (f); ponastavi (f1); ponastavi (f2); Preberi (f1, a1); Preberi (f2, a2); Medtem ko (ne EOF(f1)) in (ne EOF(f2)) začneta i:=0; j:=0; b:=res; Medtem ko se (b) in (ne EOF(f1)) in (ne EOF(f2)) začneta. Če (a1<a2) se začneZapiši (f, a1, ' '); Preberi (f1, a1); inc(i); End else begin Write(f, a2, ' '); Preberi (f2, a2); inc(j); konec; Če (i=s) ali (j=s), potem b:=false; konec; Če ni b, začnite Medtem ko (i<s) in (ne EOF(f1)) začnite Write(f, a1, '); Preberi (f1, a1); inc(i); konec; Medtem ko (j<s) in (ne EOF(f2)) začneta Write(f, a2, ' '); Preberi (f2, a2); inc(j); konec; konec; konec; Čeprav ni EOF(f1), začnite tmp:=a1; Preberi (f1, a1); Če ni EOF(f1), potem Write(f, tmp, ') drugače Write(f, tmp); konec; Čeprav ni EOF(f2), začnite tmp:=a2; Preberi (f2, a2); Če ne EOF(f2), potem Write(f, tmp, ') drugače Write(f, tmp); konec; zapreti (f); zapri (f1); zapri (f2); s:=s2; konec; Izbriši (f1); Izbriši (f2); Konec;
Vizualno je delovanje algoritma videti takole (zgoraj - neurejeno zaporedje, spodaj - urejeno).
razvrščanje zunanjih podatkov
Zelo pogosto je treba razvrstiti nekatere podatke, ki se nahajajo v zunanjem pomnilniku računalnika. V nekaterih primerih so impresivne velikosti in jih ni mogoče postaviti v RAM, da bi olajšali dostop do njih. V takih primerih se uporabljajo zunanje metode razvrščanja.
Potreba po dostopu do zunanjih medijev poslabša učinkovitost časa obdelave.
Zapletenost dela je v tem, da lahko algoritem hkrati dostopa le do enega elementa podatkovnega toka. In v tem primeru enega najboljših rezultatov kaže metoda razvrščanja z združitvijo, ki lahko primerja elemente dveh datotek zaporedoma enega za drugim.
Branje podatkov izzunanji vir, njihova obdelava in zapisovanje v končno datoteko poteka v urejenih blokih (seriji). Glede na način dela z velikostjo urejene serije obstajata dve vrsti razvrščanja: preprosto in naravno spajanje.
Enostavna združitev
S preprostim združitvijo je dolžina serije fiksna.
Tako so v izvirni nerazvrščeni datoteki vse serije sestavljene iz enega elementa. Po prvem koraku se velikost poveča na dve. Naprej - 4, 8, 16 in tako naprej.
Deluje takole:
- Izvorna datoteka (f) je razdeljena na dve pomožni - f1, f2.
- Spet so združeni v eno datoteko (f), hkrati pa se vsi elementi primerjajo v parih in tvorijo pare. Velikost serije v tem koraku postane dve.
- 1. korak se ponovi.
- Korak 2 se ponovi, vendar se že urejene 2s združijo v razvrščene 4s.
- Zanka se nadaljuje, povečuje serijo pri vsaki ponovitvi, dokler ni razvrščena celotna datoteka.
Kako veš, da je zunanje razvrščanje s preprosto združitvijo končano?
- dolžina nove serije (po združitvi) ne manjša od skupnega števila elementov;
- samo še ena epizoda;
- Pomožna datoteka f2 je ostala prazna.
Slabosti preproste združitve so: ker je dolžina izvajanja fiksna pri vsakem prehodu spajanja, bo obdelava delno urejenih podatkov trajala toliko časa kot popolnoma naključni podatki.
Naravna fuzija
Ta metoda ne omejuje dolžineserije, vendar izbere največjo možno.
Algoritem razvrščanja:
- Branje začetnega zaporedja iz datoteke f. Prvi prejeti element se zapiše v datoteko f1.
- Če naslednji vnos izpolnjuje pogoj razvrščanja, se zapiše tja, če ne, potem v drugo pomožno datoteko f2.
- Na ta način se razporedijo vsi zapisi izvorne datoteke in v f1 se oblikuje urejeno zaporedje, ki določa trenutno velikost serije.
- Datoteki f1 in f2 sta združeni.
- Cikel se ponavlja.
Zaradi nefiksirane velikosti serije je potrebno konec zaporedja označiti s posebnim znakom. Zato se pri združevanju poveča število primerjav. Poleg tega je lahko velikost ene od pomožnih datotek blizu velikosti izvirnika.
Naravna združitev je v povprečju učinkovitejša od preproste združitve z zunanjim razvrščanjem.
Značilnosti algoritma
Pri primerjavi dveh enakih vrednosti metoda ohrani njihov prvotni vrstni red, torej je stabilen.
Postopek razvrščanja je mogoče zelo uspešno razdeliti na več niti.
Videoposnetek jasno prikazuje delovanje algoritma razvrščanja z združitvijo.
