Razvrstavanje spajanjem jedan je od osnovnih algoritama računalne znanosti, koji je davne 1945. godine formulirao veliki matematičar John von Neumann. Dok je sudjelovao u Projektu Manhattan, Neumann je bio suočen s potrebom za učinkovitom obradom golemih količina podataka. Metoda koju je razvio koristila je princip "zavadi pa vladaj", što je značajno smanjilo vrijeme potrebno za rad.
Princip i korištenje algoritma
Metoda sortiranja spajanjem koristi se u problemima sortiranja struktura koje imaju naručeni pristup elementima, kao što su nizovi, liste, tokovi.
Tijekom obrade, početni blok podataka se dijeli na male komponente, do jednog elementa, koji je zapravo već sortirana lista. Zatim se ponovo sastavlja ispravnim redoslijedom.
Razvrstavanje niza određene duljine zahtijeva dodatno memorijsko područje iste veličine, u kojem se sortirani niz skuplja u dijelovima.
Metoda se može koristiti za naručivanje bilo koje usporedive vrste 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 poredana na bilo koji način koje je potrebno međusobno kombinirati kako se sortiranje ne bi prekinulo. Radi jednostavnosti sortirati ćemo brojeve uzlaznim redoslijedom.
Elementarni primjer: oba se niza 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, odnosno 18. Prema uvjetu sortiranja, broj 18 bi trebao biti prvi, jer je manji. Samo stavite brojeve ispravnim redoslijedom:
int rezultat={18, 31};
Pogledajmo kompliciraniji primjer, gdje se svaki niz sastoji od nekoliko elemenata:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritam spajanja sastojat će se od uzastopnog uspoređivanja manjih elemenata i njihovog postavljanja u rezultirajući niz ispravnim redoslijedom. Kako bismo pratili trenutne indekse, uvedimo dvije varijable - index1 i index2. U početku ih postavljamo na nulu, budući da su nizovi sortirani, a najmanji elementi su na početku.
int indeks1=0; int indeks2=0;
Napišimo cijeli proces spajanja korak po korak:
- Uzmite element s indeksom1 iz niza arr1, a element s indeksom2 iz niza arr2.
- Usporedi, odaberite najmanji od njih i staviterezultirajuć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]; indeks1++; rezultat[0]=arr1[0]; // rezultat=[2]
U drugom skretanju:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; rezultat[1]=arr2[0]; // rezultat=[2, 5]
Treći:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; rezultat[2]=arr2[1]; // rezultat=[2, 5, 6]
I tako dalje, sve 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 duljina. Što ako je jedan od trenutnih indeksa dosegao zadnji element, a u drugom nizu još uvijek ima članova?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 korak indeks1=0, indeks2=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 dosegnula je vrijednost 2, ali niz arr1 nema element s 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 potrebuuskladi trenutni indeks provjere s duljinom niza koji se spaja.
Spajanje sheme za poredane sekvence (A i B) različitih duljina:
- Ako je duljina oba niza veća od 0, usporedite A[0] i B[0] i premjestite manji u međuspremnik.
- Ako je duljina jedne od sekvenci 0, uzmite preostale elemente druge sekvence i, bez promjene njihovog redoslijeda, prijeđite na kraj međuspremnika.
Provedba druge faze
Primjer spajanja dvaju sortiranih niza u Javi dat je 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; za (int k=0; k a1.dužina-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 izvorni 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 uvjeti osiguravaju da indeksi ne prelaze veličinu niza. Treći i četvrti blok uvjeta, respektivno, premještaju se u rezultirajući niz manjeg elementa.
Podijeli 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 prijeći od izvornog nerazvrstanog niza brojeva do nekoliko sortiranih koji se mogu spojiti.
Razmotrimo prvu fazu algoritma i naučimo kako odvojiti nizove.
Ovo nije teško - izvorni popis vrijednosti podijeljen je na pola, zatim se svaki dio također rastavlja, i tako sve dok se ne dobiju vrlo mali blokovi.
Duljina takvih minimalnih elemenata može biti jednaka jedan, odnosno oni sami mogu biti sortirani niz, ali to nije nužan uvjet. Veličina bloka je unaprijed određena, a za naručivanje se može koristiti bilo koji prikladan algoritam za razvrstavanje koji učinkovito radi s nizovima malih veličina (na primjer, brzo sortiranje ili sortiranje umetanjem).
Izgleda ovako.
// izvorni niz {34, 95, 10, 2, 102, 70}; // prvo podijeliti {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 složiti.
Nakon toga morate spojiti već sortirane male nizove u parove, čuvajući redoslijed članova, što smo već naučili raditi.
Provedba prve faze
Rekurzivno particioniranje niza prikazano je ispod.
void mergeSort(T a, dug početak, dug završetak) { long split; ako(početak < završetak) { split=(start + cilj)/2; mergeSort(a, početak, split); mergeSort(a, podijeliti+1, završiti); spajanje (a, početak, razdvajanje, završetak); } }
Što se događa u ovom kodu:
-
Funkcija mergeSort dobiva početni niz
a
i lijevu i desnu granicu regije za razvrstavanje (indeksi početak i
- finish).
-
Ako je duljina ovog odjeljka veća od jedan (
početak < završetak
), tada se dijeli na dva dijela (po indeksu
- split), a svaki je rekurzivno sortiran.
-
U pozivu rekurzivne 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 izvornog odjeljka.
-
Funkcija
merge
dobiva dva uređena niza (
a[početak]…a[split]
i
- a[split +1]…a[završi) i spaja ih redoslijedom sortiranja.
Mehanika funkcije spajanja raspravlja se gore.
Opća shema algoritma
Metoda niza sortiranja spajanjem sastoji se od dva velika koraka:
- Razdijelite nesortirani izvorni niz na male komadiće.
- Sakupite ih u paru, slijedeći pravilo razvrstavanja.
Veliki i složeni zadatak raščlanjen je 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 naziva se logaritamska.
Ovo je i prednost i nedostatak metode. Njegovo vrijeme rada se ne mijenja ni u najgorem slučaju, kada se izvorni niz sortira obrnutim redoslijedom. Međutim, kada obrađuje potpuno sortirane podatke, algoritam ne daje vremenski dobitak.
Također je važno napomenuti trošak memorije metode sortiranja spajanjem. One su jednake veličini izvorne kolekcije. U ovom dodatno dodijeljenom području, sortirani niz se sastavlja od dijelova.
Provedba algoritma
Pascal sortiranje spajanjem prikazano je ispod.
Procedura MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: cijeli broj; f1, f2: tekst; b: boolean Početak:=0; Dodijeli(f, ime); reset (f); Iako nije EOF(f) početi čitati(f, a1); inc(kol); kraj; zatvori (f); Dodijeli(f1, '{naziv 1. pomoćne datoteke}'); Dodijeli(f2, '{naziv 2. pomoćne datoteke}'); s:=1; Dok (s<kol) počinje Reset(f); prepisati (f1); prepisati (f2); Za i:=1 do kol div 2 do begin Read(f, a1); Zapiši (f1, a1, ' '); kraj; Ako (kol div 2) mod s0 onda započni tmp:=kol div 2; Dok tmp mod s0 počinje Read(f, a1); Zapiši (f1, a1, ' '); inc(tmp); kraj; kraj; Iako nije EOF(f) počinje Read(f, a2); Zapiši (f2, a2, ' '); kraj; zatvori (f); zatvori (f1); zatvori (f2); prepisati (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:=točno; Dok (b) i (ne EOF(f1)) i (ne EOF(f2)) počinju ako (a1<a2) onda počinjuNapiši (f, a1, ' '); Čitaj (f1, a1); inc(i); End else begin Write(f, a2, ' '); Čitaj (f2, a2); inc(j); kraj; Ako (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; Iako nije EOF(f1) počinje tmp:=a1; Čitaj (f1, a1); Ako nije EOF(f1) onda Write(f, tmp, ') inače Write(f, tmp); kraj; Iako nije EOF(f2) počinje tmp:=a2; Čitaj (f2, a2); Ako nije EOF(f2) onda Write(f, tmp, ') inače Write(f, tmp); kraj; zatvori (f); zatvori (f1); zatvori (f2); s:=s2; kraj; Izbriši (f1); Izbriši (f2); Kraj;
Vizualno, rad algoritma izgleda ovako (gore - neuređeni niz, dolje - uređen).
Razvrstavanje vanjskih podataka
Vrlo često postoji potreba za sortiranjem nekih podataka koji se nalaze u vanjskoj memoriji računala. U nekim slučajevima su impresivne veličine i ne mogu se staviti u RAM kako bi im se olakšao pristup. U takvim slučajevima koriste se vanjske metode razvrstavanja.
Potreba za pristupom vanjskim medijima smanjuje učinkovitost vremena obrade.
Složenost posla je u tome što algoritam može pristupiti samo jednom elementu toka podataka odjednom. I u ovom slučaju, jedan od najboljih rezultata pokazuje metoda sortiranja spajanjem, koja može usporediti elemente dviju datoteka uzastopce jedan za drugim.
Čitanje podataka izvanjski izvor, njihova se obrada i upis u konačnu datoteku provode u uređenim blokovima (serijama). Prema načinu rada s veličinom naručenih serija postoje dvije vrste sortiranja: jednostavno i prirodno spajanje.
Jednostavno spajanje
Jednostavnim spajanjem, duljina serije je fiksna.
Dakle, u izvornoj nerazvrstanoj datoteci, 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:
- Izvorna datoteka (f) podijeljena je na dvije pomoćne - f1, f2.
- Opet su spojeni u jednu datoteku (f), ali se u isto vrijeme svi elementi uspoređuju u parovima i oblikuju 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 niz na svakoj iteraciji, sve dok se cijela datoteka 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ćna datoteka f2 ostala je prazna.
Nedostaci jednostavnog spajanja su: budući da je duljina rada fiksna na svakom prolazu spajanja, djelomično uređenim podacima trebat će isto toliko vremena da se obrađuju kao i potpuno slučajni podaci.
Prirodna fuzija
Ova metoda ne ograničava duljinuserija, ali bira maksimalno mogući.
Algoritam sortiranja:
- Čitanje početnog niza iz datoteke f. Prvi primljeni element upisuje se u datoteku f1.
- Ako sljedeći unos zadovoljava uvjet sortiranja, upisuje se tamo, ako ne, onda u drugu pomoćnu datoteku f2.
- Na taj se način 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 usporedbi. Osim toga, veličina jedne od pomoćnih datoteka može biti bliska veličini originala.
U prosjeku, prirodno spajanje je učinkovitije od jednostavnog spajanja s vanjskim razvrstavanjem.
Značajke algoritma
Kada se uspoređuju dvije identične vrijednosti, metoda čuva njihov izvorni redoslijed, odnosno stabilna je.
Proces sortiranja može se vrlo uspješno podijeliti u više niti.
Videozapis jasno pokazuje rad algoritma sortiranja spajanjem.
