Sujungti rūšiavimą yra vienas iš pagrindinių informatikos algoritmų, kurį 1945 m. suformulavo didysis matematikas Johnas von Neumannas. Dalyvaudamas Manheteno projekte, Neumannas susidūrė su būtinybe efektyviai apdoroti didžiulius duomenų kiekius. Jo sukurtame metode buvo naudojamas principas „skaldyk ir valdyk“, kuris žymiai sumažino darbui reikalingą laiką.
Algoritmo principas ir naudojimas
Sujungimo rūšiavimo metodas naudojamas rūšiuojant struktūras, kurios užsakė prieigą prie elementų, pvz., masyvų, sąrašų, srautų.
Apdorojimo metu pradinis duomenų blokas suskaidomas į mažus komponentus, iki vieno elemento, kuris iš tikrųjų jau yra surūšiuotas sąrašas. Tada jis surenkamas teisinga tvarka.
Norint rūšiuoti tam tikro ilgio masyvą, reikia papildomos tokio pat dydžio atminties srities, kurioje surūšiuotas masyvas surenkamas dalimis.
Šis metodas gali būti naudojamas norint užsisakyti bet kokį palyginamų duomenų tipą, pvz., skaičius ar eilutes.
Sujungti surūšiuotasiužetai
Kad suprastume algoritmą, jo analizę pradėkime nuo pabaigos – nuo surūšiuotų blokų sujungimo mechanizmo.
Įsivaizduokime, kad turime du bet kokiu būdu surūšiuotus skaičių masyvus, kuriuos reikia derinti tarpusavyje, kad rūšiavimas nenutrūktų. Kad būtų paprasčiau, skaičius surūšiuosime didėjančia tvarka.
Elementarus pavyzdys: abu masyvus sudaro po vieną elementą.
int arr1={31}; int arr2={18};
Norėdami juos sujungti, turite paimti pirmojo masyvo nulinį elementą (nepamirškite, kad numeracija prasideda nuo nulio) ir antrojo masyvo nulinį elementą. Tai yra atitinkamai 31 ir 18. Pagal rūšiavimo sąlygą skaičius 18 turėtų būti pirmas, nes jis yra mažesnis. Tiesiog sudėkite skaičius teisinga tvarka:
int rezultatas={18, 31};
Pažiūrėkime į sudėtingesnį pavyzdį, kur kiekvienas masyvas susideda iš kelių elementų:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Sujungimo algoritmą sudarys nuoseklus mažesnių elementų palyginimas ir jų įdėjimas į gautą masyvą teisinga tvarka. Norėdami sekti esamus indeksus, įveskime du kintamuosius – index1 ir index2. Iš pradžių nustatome juos į nulį, nes masyvai yra rūšiuojami, o mažiausi elementai yra pradžioje.
int index1=0; int index2=0;
Parašykime visą sujungimo procesą žingsnis po žingsnio:
- Paimkite elementą su indeksu1 iš masyvo arr1 ir elementą su indeksu2 iš masyvo arr2.
- Palyginkite, pasirinkite mažiausią iš jų ir įdėkitegautas masyvas.
- Padidinkite dabartinį mažesnio elemento indeksą 1.
- Tęskite nuo pirmojo žingsnio.
Pirmoje orbitoje situacija atrodys taip:
indeksas1=0; indeksas2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; rezultatas[0]=arr1[0]; // rezultatas=[2]
Antrame posūkyje:
indeksas1=1; indeksas2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; rezultatas[1]=arr2[0]; // rezultatas=[2, 5]
Trečia:
indeksas1=1; indeksas2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; rezultatas[2]=arr2[1]; // rezultatas=[2, 5, 6]
Ir taip toliau, kol rezultatas bus visiškai surūšiuotas masyvas: {2, 5, 6, 17, 21, 19, 30, 45}.
Sujungiant skirtingo ilgio masyvus, gali kilti tam tikrų sunkumų. Ką daryti, jei vienas iš dabartinių indeksų pasiekė paskutinį elementą, o antrajame masyve vis dar liko narių?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 žingsnis indeksas1=0, indeksas2=0; 1 2 rezultatas={1, 2}; // 3 žingsnių indeksas1=1, indeksas2=1; 4 < 5 rezultatas={1, 2, 4}; //4 žingsnio indeksas1=2, indeksas2=1 ??
Kintamasis indeksas1 pasiekė 2 reikšmę, bet arr1 masyve nėra elemento su tokiu indeksu. Čia viskas paprasta: tereikia perkelti likusius antrojo masyvo elementus į gautą, išsaugant jų tvarką.
rezultatas={1, 2, 4, 5, 6, 7, 9};
Ši situacija rodo, kad mums reikiasuderinkite dabartinį patikrinimo indeksą su jungiamo masyvo ilgiu.
Sujungti skirtingo ilgio užsakytų sekų (A ir B) schemą:
- Jei abiejų sekų ilgis yra didesnis nei 0, palyginkite A[0] ir B[0] ir perkelkite mažesnę į buferį.
- Jei vienos iš sekų ilgis yra 0, paimkite likusius antrosios sekos elementus ir, nekeisdami jų tvarkos, pereikite prie buferio pabaigos.
Antrojo etapo įgyvendinimas
Dviejų surūšiuotų masyvų sujungimo Java programoje pavyzdys pateiktas toliau.
int a1=naujas int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=naujas int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=naujas int[a1.ilgis + a2.ilgis]; int i=0, j=0; for (int k=0; k a1.ilgis-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.ilgis-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++; } }
Čia:
- a1 ir a2 yra pradiniai surūšiuoti masyvai, kuriuos reikia sujungti;
- a3 – galutinis masyvas;
- i ir j yra dabartinių masyvų a1 ir a2 elementų indeksai.
Pirmoji ir antroji if sąlygos užtikrina, kad indeksai neviršytų masyvo dydžio. Trečiasis ir ketvirtasis sąlygų blokai atitinkamai perkeliami į gautą mažesnio elemento masyvą.
Skaldyk ir valdyk
Taigi, išmokome sujungti surūšiuotusvertybių rinkiniai. Galima sakyti, kad antroji sujungimo rūšiavimo algoritmo dalis – pats suliejimas – jau surūšiuota.
Tačiau vis tiek turite suprasti, kaip iš pradinio nerūšiuoto skaičių masyvo pereiti prie kelių surūšiuotų skaičių, kuriuos galima sujungti.
Panagrinėkime pirmąjį algoritmo etapą ir sužinokime, kaip atskirti masyvus.
Tai nesunku – pradinis reikšmių sąrašas padalijamas per pusę, tada kiekviena dalis taip pat padalinama į dvi dalis ir taip toliau, kol gaunami labai maži blokeliai.
Tokių minimalių elementų ilgis gali būti lygus vienetui, tai yra, jie patys gali būti surūšiuotas masyvas, tačiau tai nėra būtina sąlyga. Bloko dydis nustatomas iš anksto ir norint jį užsisakyti galima naudoti bet kokį tinkamą rūšiavimo algoritmą, kuris efektyviai veikia su mažo dydžio masyvais (pavyzdžiui, greitasis rūšiavimas arba įterpimo rūšiavimas).
Atrodo taip.
// originalus masyvas {34, 95, 10, 2, 102, 70}; // pirmasis padalijimas {34, 95, 10} ir {2, 102, 70}; // sekundės padalijimas {34} ir {95, 10} ir {2} ir {102, 70}
Gautus blokus, sudarytus iš 1–2 elementų, labai lengva išdėstyti.
Po to reikia sujungti jau surūšiuotus mažus masyvus poromis, išsaugant narių tvarką, ką jau išmokome daryti.
Pirmojo etapo įgyvendinimas
Rekursyvus masyvo skaidymas parodytas žemiau.
void mergeSort(T a, ilga pradžia, ilga pabaiga) { long split; jeigu(pradžia < finišas) { padalijimas=(pradžia + finišas)/2; mergeSort(a, pradžia, padalijimas); mergeSort(a, padalijimas+1, pabaiga); merge(a, start, split, finish); } }
Kas vyksta šiame kode:
-
Funkcija mergeSort gauna pradinį masyvą
a
ir kairiąsias bei dešiniąsias rūšiuojamo regiono ribas (indeksų pradžia ir
- finish).
-
Jei šios atkarpos ilgis yra didesnis nei vienas (
pradžia < finišas
), tada ji padalyta į dvi dalis (pagal indeksą
- split), ir kiekvienas iš jų rūšiuojamas rekursyviai.
-
Rekursyvios funkcijos iškvietime kairėje pusėje perduodamas brėžinio pradinis indeksas ir indeksas
split
. Atitinkamai dešiniojo pradžia bus
- (skilimas + 1), o pabaiga bus paskutinė pradinės dalies rodyklė.
Funkcija Nr. +1]…a[baigti
) ir sujungia juos rūšiavimo tvarka.
Sujungimo funkcijos mechanika aptarta aukščiau.
Bendra algoritmo schema
Sujungimo rūšiavimo masyvo metodas susideda iš dviejų didelių žingsnių:
- Padalykite nerūšiuotą pradinį masyvą į mažas dalis.
- Surinkite juos poromis, vadovaudamiesi rūšiavimo taisykle.
Didelė ir sudėtinga užduotis suskaidoma į daugybę paprastų, kurios išsprendžiamos nuosekliai ir pasiekiamas norimas rezultatas.
Metodo įvertinimas
Sujungimo rūšiavimo sudėtingumą laike lemia padalijimo medžio aukštisalgoritmas ir yra lygus elementų skaičiui masyve (n) padauginus iš jo logaritmo (log n). Toks įvertinimas vadinamas logaritminiu.
Tai ir metodo privalumas, ir trūkumas. Jo veikimo laikas nesikeičia net ir blogiausiu atveju, kai pradinis masyvas rūšiuojamas atvirkštine tvarka. Tačiau apdorojant visiškai surūšiuotus duomenis, algoritmas nepateikia laiko padidėjimo.
Taip pat svarbu atkreipti dėmesį į atminties sąnaudas taikant sujungimo rūšiavimo metodą. Jie prilygsta originalios kolekcijos dydžiui. Šioje papildomai paskirtoje srityje iš dalių surenkamas surūšiuotas masyvas.
Algoritmo įgyvendinimas
Pascal sujungimo rūšiavimas parodytas žemiau.
Procedure MergeSort(vardas: eilutė; var f: tekstas); Var a1, a2, s, i, j, kol, tmp: sveikasis skaičius; f1, f2: tekstas; b: loginis Pradžia:=0; Priskirti(f, vardas); atstatyti(f); Nors ne EOF(f), pradeda skaityti(f, a1); inc(col); pabaiga; uždaryti(f); Assign(f1, '{1-ojo pagalbinio failo pavadinimas}'); Assign(f2, '{2-ojo pagalbinio failo pavadinimas}'); s:=1; Nors (s<kol) pradėkite Reset (f); perrašyti(f1); perrašyti(f2); Jei i:=1 į kol div 2, pradėkite Read(f, a1); Write(f1, a1, ' '); pabaiga; Jei (kol div 2) mod s0, tada prasideda tmp:=kol div 2; Nors tmp mod s0 pradeda skaityti (f, a1); Write(f1, a1, ' '); inc(tmp); pabaiga; pabaiga; Nors ne EOF(f), pradeda skaityti(f, a2); Write(f2, a2, ' '); pabaiga; uždaryti(f); uždaryti(f1); uždaryti(f2); perrašyti(f); atstatyti (f1); atstatyti (f2); Skaityti(f1, a1); Skaityti(f2, a2); Nors (ne EOF(f1)) ir (ne EOF(f2)) prasideda i:=0; j:=0; b:=tiesa; Nors (b) ir (ne EOF(f1)) ir (ne EOF(f2)) prasideda If (a1<a2), tada prasidedaWrite(f, a1, ' '); Skaityti(f1, a1); inc(i); Pabaiga kita pradžia Rašyti(f, a2, ' '); Skaityti(f2, a2); inc(j); pabaiga; Jei (i=s) arba (j=s), tai b:=klaidinga; pabaiga; Jei ne b, tada pradėkite Nors (i<s) ir (ne EOF(f1)) pradėkite Write(f, a1, ' '); Skaityti(f1, a1); inc(i); pabaiga; Nors (j<s) ir (ne EOF(f2)) pradeda Write(f, a2, '); Skaityti(f2, a2); inc(j); pabaiga; pabaiga; pabaiga; Nors ne EOF(f1), pradėkite tmp:=a1; Skaityti(f1, a1); Jei ne EOF(f1), tada Write(f, tmp, ' ') else Write(f, tmp); pabaiga; Nors ne EOF(f2), pradėkite tmp:=a2; Skaityti(f2, a2); Jei ne EOF(f2), tada Write(f, tmp, ' ') else Write(f, tmp); pabaiga; uždaryti(f); uždaryti(f1); uždaryti(f2); s:=s2; pabaiga; Ištrinti(f1); Ištrinti (f2); Pabaiga;
Vizualiai algoritmo veikimas atrodo taip (viršuje – netvarkinga seka, apačioje – tvarka).
Išorinis duomenų rūšiavimas
Labai dažnai reikia rūšiuoti kai kuriuos duomenis, esančius išorinėje kompiuterio atmintyje. Kai kuriais atvejais jie yra įspūdingo dydžio ir negali būti dedami į RAM, kad būtų lengviau prieiti. Tokiais atvejais naudojami išoriniai rūšiavimo metodai.
Būtinybė pasiekti išorinę laikmeną mažina apdorojimo laiko efektyvumą.
Darbo sudėtingumas yra tas, kad algoritmas vienu metu gali pasiekti tik vieną duomenų srauto elementą. Ir šiuo atveju vieną geriausių rezultatų rodo sujungimo rūšiavimo metodas, kuris gali palyginti dviejų failų elementus nuosekliai vienas po kito.
Nuskaitomi duomenys išišorinis š altinis, jų apdorojimas ir įrašymas į galutinį failą atliekamas sutvarkytais blokais (serija). Atsižvelgiant į darbo su užsakytų serijų dydžiu būdą, yra dviejų tipų rūšiavimas: paprastas ir natūralus sujungimas.
Paprastas sujungimas
Paprastu sujungimu serijos ilgis fiksuojamas.
Taigi pradiniame nerūšiuotame faile visos serijos susideda iš vieno elemento. Po pirmojo žingsnio dydis padidėja iki dviejų. Kitas – 4, 8, 16 ir tt.
Tai veikia taip:
- Š altinio failas (f) padalintas į du pagalbinius – f1, f2.
- Jie vėl sujungiami į vieną failą (f), bet tuo pačiu metu visi elementai lyginami poromis ir sudaro poras. Šiame žingsnyje serijos dydis tampa du.
- 1 veiksmas kartojamas.
- 2 veiksmas kartojamas, bet jau užsakyti 2 sujungiami į surūšiuotas 4s.
- Cilpa tęsiasi, didinant seriją kiekvienoje iteracijoje, kol visas failas bus surūšiuotas.
Kaip žinoti, kad išorinis rūšiavimas paprastu sujungimu baigtas?
- naujos serijos ilgis (sujungus) ne mažesnis už bendrą elementų skaičių;
- liko tik viena serija;
- Pagalbinis failas f2 paliktas tuščias.
Paprasto sujungimo trūkumai yra šie: kadangi vykdymo trukmė yra fiksuota kiekviename sujungimo etape, iš dalies sutvarkytų duomenų apdorojimas užtruks tiek pat laiko, kiek ir visiškai atsitiktiniai duomenys.
Natūrali sintezė
Šis metodas neriboja ilgioseriją, bet pasirenka maksimaliai įmanomą.
Rūšiavimo algoritmas:
- Pradinės sekos skaitymas iš failo f. Pirmasis gautas elementas įrašomas į failą f1.
- Jei kitas įrašas tenkina rūšiavimo sąlygą, jis rašomas ten, jei ne, tada į antrą pagalbinį failą f2.
- Tokiu būdu paskirstomi visi š altinio failo įrašai, o f1 formuojama sutvarkyta seka, kuri nustato esamą serijos dydį.
- F1 ir f2 failai yra sujungti.
- Citas kartojasi.
Dėl nefiksuoto serijos dydžio, sekos pabaigą būtina pažymėti specialiu simboliu. Todėl sujungiant palyginimų daugėja. Be to, vieno iš pagalbinių failų dydis gali būti artimas originalo dydžiui.
Vidutiniškai natūralus sujungimas yra efektyvesnis nei paprastas sujungimas su išoriniu rūšiavimu.
Algoritmo ypatybės
Lyginant dvi identiškas reikšmes, metodas išsaugo pradinę jų tvarką, tai yra, jis yra stabilus.
Rūšiavimo procesą galima labai sėkmingai suskaidyti į kelias gijas.
Vaizdo įrašas aiškiai parodo sujungimo rūšiavimo algoritmo veikimą.
