Razvrstavanje spajanjem je jedan od osnovnih algoritama kompjuterske nauke, koji je davne 1945. godine formulisao veliki matematičar Džon fon Nojman. Dok je učestvovao u projektu Manhattan, Nojman se suočio sa potrebom da efikasno obradi ogromne količine podataka. Metoda koju je razvio koristila je princip "zavadi pa vladaj", što je značajno smanjilo vrijeme potrebno za rad.
Princip i upotreba algoritma
Metod sortiranja spajanjem se koristi u problemima sortiranja struktura koje imaju uređen pristup elementima, kao što su nizovi, liste, tokovi.
Tokom obrade, početni blok podataka se dijeli na male komponente, do jednog elementa, koji je u stvari već sortirana lista. Zatim se ponovo sastavlja ispravnim redoslijedom.
Sortiranje niza određene dužine zahtijeva dodatnu memorijsku oblast iste veličine, u kojoj se sortirani niz skuplja u dijelovima.
Metoda se može koristiti za naručivanje bilo kojeg uporedivog tipa podataka, kao što su brojevi ili nizovi.
Spoji sortiranoparcele
Da bismo razumjeli algoritam, počnimo njegovu analizu od kraja - od mehanizma spajanja sortiranih blokova.
Zamislimo da imamo dva niza brojeva sortiranih na bilo koji način koje je potrebno međusobno kombinovati kako se sortiranje ne bi prekinulo. Radi jednostavnosti, sortiraćemo brojeve u rastućem redosledu.
Elementarni primjer: oba niza se sastoje od po jednog elementa.
int arr1={31}; int arr2={18};
Da biste ih spojili, trebate uzeti nulti element prvog niza (ne zaboravite da numeriranje počinje od nule) i nulti element drugog niza. To su, redom, 31 i 18. Prema uslovu sortiranja, broj 18 bi trebao biti prvi, jer je manji. Samo stavite brojeve ispravnim redoslijedom:
int rezultat={18, 31};
Pogledajmo složeniji primjer, gdje se svaki niz sastoji od nekoliko elemenata:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritam spajanja će se sastojati od sekvencijalnog poređenja manjih elemenata i njihovog postavljanja u rezultirajući niz ispravnim redoslijedom. Da bismo pratili trenutne indekse, uvedimo dvije varijable - index1 i index2. U početku ih postavljamo na nulu, pošto su nizovi sortirani, a najmanji elementi su na početku.
int index1=0; int index2=0;
Napišimo cijeli proces spajanja korak po korak:
- Uzmite element sa indeksom1 iz niza arr1, a element sa indeksom2 iz niza arr2.
- Uporedi, odaberite najmanji od njih i ubaciterezultirajući niz.
- Povećajte trenutni indeks manjeg elementa za 1.
- Nastavite od prvog koraka.
Na prvoj orbiti situacija će izgledati ovako:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; rezultat[0]=arr1[0]; // rezultat=[2]
Na drugom skretanju:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; rezultat[1]=arr2[0]; // rezultat=[2, 5]
Treći:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; rezultat[2]=arr2[1]; // rezultat=[2, 5, 6]
I tako dalje, dok rezultat ne bude potpuno sortiran niz: {2, 5, 6, 17, 21, 19, 30, 45}.
Određene poteškoće mogu nastati ako se spoje nizovi različitih dužina. Šta ako je jedan od trenutnih indeksa stigao do posljednjeg elementa, a u drugom nizu još uvijek ima članova?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 korak index1=0, index2=0; 1 2 rezultat={1, 2}; // 3 koraka index1=1, index2=1; 4 < 5 rezultat={1, 2, 4}; //4 koraka index1=2, index2=1 ??
Varijabla index1 je dostigla vrijednost 2, ali niz arr1 nema element sa tim indeksom. Ovdje je sve jednostavno: samo prenesite preostale elemente drugog niza u rezultirajući, čuvajući njihov redoslijed.
rezultat={1, 2, 4, 5, 6, 7, 9};
Ova situacija nam ukazuje na potrebuuskladiti trenutni indeks provjere sa dužinom niza koji se spaja.
Spajanje šeme za uređene sekvence (A i B) različitih dužina:
- Ako je dužina oba niza veća od 0, uporedite A[0] i B[0] i premjestite manji u bafer.
- Ako je dužina jedne od sekvenci 0, uzmite preostale elemente druge sekvence i, bez promjene njihovog redoslijeda, pređite na kraj bafera.
Provedba druge faze
Primjer spajanja dva sortirana niza u Javi je dat ispod.
int a1=novi int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=novi 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; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
Ovdje:
- a1 i a2 su originalni sortirani nizovi koji se spajaju;
- a3 – konačni niz;
- i i j su indeksi trenutnih elemenata za nizove a1 i a2.
Prvi i drugi ako uslovi osiguravaju da indeksi ne prelaze veličinu niza. Treći i četvrti blok uslova, respektivno, se pomeraju u rezultujući niz manjeg elementa.
Zavadi pa vladaj
Dakle, naučili smo spojiti sortiranozbirke vrijednosti. Može se reći da je drugi dio algoritma sortiranja spajanjem - samo spajanje - već sortiran.
Međutim, još uvijek morate razumjeti kako od originalnog nesortiranog niza brojeva doći do nekoliko sortiranih koji se mogu spojiti.
Razmotrimo prvu fazu algoritma i naučimo kako razdvojiti nizove.
Ovo nije teško - originalna lista vrijednosti je podijeljena na pola, zatim se svaki dio također rastavlja, i tako sve dok se ne dobiju vrlo mali blokovi.
Dužina takvih minimalnih elemenata može biti jednaka jedan, odnosno oni sami mogu biti sortirani niz, ali to nije neophodan uslov. Veličina bloka je unaprijed određena, a za naručivanje se može koristiti bilo koji odgovarajući algoritam za sortiranje koji efikasno radi s nizovima malih veličina (na primjer, brzo sortiranje ili sortiranje umetanjem).
Izgleda ovako.
// originalni niz {34, 95, 10, 2, 102, 70}; // prva podjela {34, 95, 10} i {2, 102, 70}; // drugi split {34} i {95, 10} i {2} i {102, 70}
Rezultirajuće blokove, koji se sastoje od 1-2 elementa, vrlo je lako rasporediti.
Nakon toga, potrebno je spojiti već sortirane male nizove u parove, čuvajući redoslijed članova, što smo već naučili raditi.
Provedba prve faze
Rekurzivno particioniranje niza je prikazano ispod.
void mergeSort(T a, dug početak, dug završetak) { long split; ako(početak < završetak) { split=(start + završetak)/2; mergeSort(a, početak, split); mergeSort(a, split+1, end); merge(a, početak, razdvajanje, završetak); } }
Šta se događa u ovom kodu:
-
funkcija mergeSort dobiva početni niz
a
i lijevu i desnu ivicu regije za sortiranje (indeksi početak i
- finish).
-
Ako je dužina ovog dijela veća od jedan (
početak < završetak
), tada se dijeli na dva dijela (po indeksu
- split), a svaki je rekurzivno sortiran.
-
U rekurzivnom pozivu funkcije za lijevu stranu, prosljeđuju se početni indeks dijagrama i indeks
split
. Za desnu, redom, početak će biti
- (split + 1), a kraj će biti posljednji indeks originalnog odjeljka.
-
Funkcija
spajanje
dobiva dvije uređene sekvence (
a[početak]…a[split]
i
- a[split +1]…a[završi) i spaja ih po redoslijedu sortiranja.
Mehanika funkcije spajanja je diskutovana iznad.
Opšta šema algoritma
Metoda niza sortiranja spajanjem sastoji se od dva velika koraka:
- Razdijelite nesortirani originalni niz na male komade.
- Sakupite ih u paru, prateći pravilo sortiranja.
Veliki i složeni zadatak se raščlanjuju na mnogo jednostavnih, koji se uzastopno rješavaju, što dovodi do željenog rezultata.
Procjena metode
Vremenska složenost sortiranja spajanjem određena je visinom podijeljenog stablaalgoritam i jednak je broju elemenata u nizu (n) pomnoženom njegovom logaritmu (log n). Takva procjena se naziva logaritamska.
Ovo je i prednost i nedostatak metode. Njegovo vrijeme rada se ne mijenja čak ni u najgorem slučaju, kada se originalni niz sortira obrnutim redoslijedom. Međutim, prilikom obrade potpuno sortiranih podataka, algoritam ne daje vremensku dobit.
Takođe je važno napomenuti troškove memorije metode sortiranja spajanjem. One su jednake veličini originalne kolekcije. U ovom dodatno dodijeljenom području, sortirani niz se sastavlja od dijelova.
Implementacija algoritma
Pascal sortiranje spajanjem je prikazano ispod.
Procedura MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: cijeli broj; f1, f2: tekst; b: boolean Begincol:=0; Dodijeli(f, ime); reset (f); Dok nije EOF(f) počinje čitanje(f, a1); inc(kol); kraj; zatvori(f); Assign(f1, '{ime 1. pomoćnog fajla}'); Assign(f2, '{ime 2. pomoćne datoteke}'); s:=1; Dok (s<kol) počinje Reset(f); prepisati (f1); rewrite(f2); Za i:=1 do kol div 2 do begin Read(f, a1); Write(f1, a1, ' '); kraj; Ako (kol div 2) mod s0 onda počinje tmp:=kol div 2; Dok tmp mod s0 počinje Read(f, a1); Write(f1, a1, ' '); inc(tmp); kraj; kraj; Dok nije EOF(f) počinje Read(f, a2); Write(f2, a2, ' '); kraj; zatvori(f); zatvori(f1); zatvori(f2); rewrite(f); reset (f1); reset (f2); Čitaj(f1, a1); Čitaj(f2, a2); Dok (ne EOF(f1)) i (ne EOF(f2)) počinju i:=0; j:=0; b:=true; Dok (b) i (ne EOF(f1)) i (ne EOF(f2)) počinju ako (a1<a2) onda počinjuWrite(f, a1, ' '); Čitaj(f1, a1); inc(i); End else begin Write(f, a2, ' '); Čitaj(f2, a2); inc(j); kraj; Ako je (i=s) ili (j=s) onda b:=false; kraj; Ako nije b, onda počinje While (i<s) i (ne EOF(f1)) počinje Write(f, a1, ' '); Čitaj(f1, a1); inc(i); kraj; Dok (j<s) i (ne EOF(f2)) počinju Write(f, a2, ' '); Čitaj(f2, a2); inc(j); kraj; kraj; kraj; Dok nije EOF(f1) počinje tmp:=a1; Čitaj(f1, a1); Ako nije EOF(f1) onda Write(f, tmp, ') inače Write(f, tmp); kraj; Dok nije EOF(f2) počinje tmp:=a2; Čitaj(f2, a2); Ako nije EOF(f2) onda Write(f, tmp, ' ') else Write(f, tmp); kraj; zatvori(f); zatvori(f1); zatvori(f2); s:=s2; kraj; Obriši (f1); Obriši (f2); Kraj;
Vizuelno, rad algoritma izgleda ovako (gore - neuređeni niz, donji - uređen).
Spoljno sortiranje podataka
Vrlo često postoji potreba za sortiranjem nekih podataka koji se nalaze u eksternoj memoriji računara. U nekim slučajevima su impresivne veličine i ne mogu se staviti u RAM kako bi im se olakšao pristup. Za takve slučajeve koriste se eksterne metode sortiranja.
Potreba za pristupom eksternim medijima smanjuje efikasnost vremena obrade.
Složenost posla je u tome što algoritam može pristupiti samo jednom elementu toka podataka istovremeno. I u ovom slučaju, jedan od najboljih rezultata pokazuje metoda sortiranja spajanjem, koja može porediti elemente dva fajla uzastopno jedan za drugim.
Čitanje podataka saeksterni izvor, njihova obrada i upisivanje u konačnu datoteku se odvijaju u uređenim blokovima (serijama). Prema načinu rada sa veličinom naručenih serija, postoje dvije vrste sortiranja: jednostavno i prirodno spajanje.
Jednostavno spajanje
Sa jednostavnim spajanjem, dužina serije je fiksna.
Dakle, u originalnom nesortiranom fajlu, sve serije se sastoje od jednog elementa. Nakon prvog koraka, veličina se povećava na dva. Sljedeće - 4, 8, 16 i tako dalje.
Radi ovako:
- Izvorni fajl (f) je podijeljen na dva pomoćna - f1, f2.
- Opet se spajaju u jedan fajl (f), ali se istovremeno svi elementi porede u parovima i formiraju parove. Veličina serije u ovom koraku postaje dva.
- Korak 1 se ponavlja.
- Korak 2 se ponavlja, ali već naručene 2s se spajaju u sortirane 4s.
- Petlja se nastavlja, povećavajući seriju na svakoj iteraciji, sve dok se cijeli fajl ne sortira.
Kako znate da je vanjsko sortiranje jednostavnim spajanjem završeno?
- dužina nove serije (nakon spajanja) ne manje od ukupnog broja elemenata;
- preostala je samo jedna epizoda;
- Pomoćni fajl f2 je ostavljen prazan.
Nedostaci jednostavnog spajanja su: pošto je dužina rada fiksirana na svakom prolazu spajanja, djelomično uređenim podacima će biti potrebno isto toliko vremena da se obrađuju kao i potpuno nasumični podaci.
Prirodna fuzija
Ova metoda ne ograničava dužinuserija, ali bira maksimalno mogući.
Algoritam sortiranja:
- Čitanje početnog niza iz datoteke f. Prvi primljeni element se upisuje u datoteku f1.
- Ako naredni unos zadovoljava uslov sortiranja, upisuje se tamo, ako ne, onda u drugi pomoćni fajl f2.
- Na ovaj način se distribuiraju svi zapisi izvorne datoteke i formira se uređeni niz u f1, koji određuje trenutnu veličinu serije.
- Datoteke f1 i f2 su spojene.
- Ciklus se ponavlja.
Zbog nefiksne veličine serije, potrebno je kraj niza označiti posebnim znakom. Stoga se pri spajanju povećava broj poređenja. Osim toga, veličina jednog od pomoćnih fajlova može biti bliska veličini originala.
U prosjeku, prirodno spajanje je efikasnije od jednostavnog spajanja s vanjskim sortiranjem.
Karakteristike algoritma
Kada se uporede dvije identične vrijednosti, metoda čuva njihov originalni poredak, odnosno stabilna je.
Proces sortiranja se može vrlo uspješno podijeliti u više niti.
Video snimak jasno pokazuje rad algoritma sortiranja spajanjem.
