Merge sort er en av de grunnleggende datavitenskapelige algoritmene, formulert tilbake i 1945 av den store matematikeren John von Neumann. Mens han deltok i Manhattan-prosjektet, ble Neumann møtt med behovet for å effektivt behandle enorme mengder data. Metoden han utviklet brukte prinsippet om «del og hersk», noe som reduserte arbeidstiden betydelig.
Prinsipp og bruk av algoritmen
Flettesorteringsmetoden brukes i problemer med sortering av strukturer som har bestilt tilgang til elementer, for eksempel arrays, lister, streams.
Under behandlingen deles den innledende datablokken i små komponenter, opptil ett element, som faktisk allerede er en sortert liste. Deretter settes den sammen i riktig rekkefølge.
Sortering av en matrise med en viss lengde krever et ekstra minneområde av samme størrelse, der den sorterte matrisen er samlet i deler.
Metoden kan brukes til å bestille alle sammenlignbare datatyper, for eksempel tall eller strenger.
Flette sorterttomter
For å forstå algoritmen, la oss starte analysen fra slutten - fra mekanismen for å slå sammen sorterte blokker.
La oss forestille oss at vi har to tallserier sortert på noen måte som må kombineres med hverandre slik at sorteringen ikke brytes. For enkelhets skyld sorterer vi tallene i stigende rekkefølge.
Elementært eksempel: begge arrays består av ett element hver.
int arr1={31}; int arr2={18};
For å slå dem sammen, må du ta null-elementet til den første matrisen (ikke glem at nummereringen starter fra null) og null-elementet til den andre matrisen. Disse er henholdsvis 31 og 18. I følge sorteringsbetingelsen skal tallet 18 komme først, siden det er mindre. Bare legg inn tallene i riktig rekkefølge:
int resultat={18, 31};
La oss se på et mer komplisert eksempel, der hver matrise består av flere elementer:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Flettealgoritmen vil bestå av å sekvensielt sammenligne mindre elementer og plassere dem i den resulterende matrisen i riktig rekkefølge. For å holde styr på gjeldende indekser, la oss introdusere to variabler - indeks1 og indeks2. Til å begynne med satte vi dem til null, siden matrisene er sortert, og de minste elementene er i begynnelsen.
int index1=0; int index2=0;
La oss skrive hele sammenslåingsprosessen trinn for trinn:
- Ta elementet med index1 fra arrayen arr1, og elementet med index2 fra arrayen arr2.
- Sammenlign, velg den minste av dem og legg innresulterende matrise.
- Øk gjeldende indeks for det mindre elementet med 1.
- Fortsett fra første trinn.
På den første bane vil situasjonen se slik ut:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; resultat[0]=arr1[0]; // resultat=[2]
På andre sving:
index1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; resultat[1]=arr2[0]; // resultat=[2, 5]
Tredje:
index1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; resultat[2]=arr2[1]; // resultat=[2, 5, 6]
Og så videre, til resultatet er en fullstendig sortert matrise: {2, 5, 6, 17, 21, 19, 30, 45}.
Vise vanskeligheter kan oppstå hvis arrays med forskjellige lengder slås sammen. Hva om en av de gjeldende indeksene har nådd det siste elementet, og det fortsatt er medlemmer igjen i den andre matrisen?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 trinn indeks1=0, indeks2=0; 1 2 resultat={1, 2}; // 3 trinns indeks1=1, indeks2=1; 4 < 5 resultat={1, 2, 4}; //4 trinns indeks1=2, indeks2=1 ??
Indeks1-variabelen har nådd verdien 2, men arr1-matrisen har ikke et element med den indeksen. Alt er enkelt her: bare overfør de gjenværende elementene i den andre matrisen til den resulterende, og bevar rekkefølgen deres.
resultat={1, 2, 4, 5, 6, 7, 9};
Denne situasjonen indikerer behovet for ossmatch gjeldende sjekkindeks med lengden på matrisen som slås sammen.
Fletteskjema for ordnede sekvenser (A og B) av forskjellige lengder:
- Hvis lengden på begge sekvensene er større enn 0, sammenlign A[0] og B[0] og flytt den minste til bufferen.
- Hvis lengden på en av sekvensene er 0, ta de gjenværende elementene i den andre sekvensen og, uten å endre rekkefølgen, gå til slutten av bufferen.
Implementering av andre trinn
Et eksempel på å slå sammen to sorterte arrays i Java er gitt nedenfor.
int a1=ny int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=ny int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.lengde-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++; } annet { int b=a2[j]; a3[k]=b; j++; } }
Her:
- a1 og a2 er de originale sorterte matrisene som skal slås sammen;
- a3 – siste array;
- i og j er indekser for gjeldende elementer for matrisene a1 og a2.
De første og andre hvis-forholdene sikrer at indeksene ikke går utover størrelsen på matrisen. Den tredje og fjerde betingelsesblokken flyttes til den resulterende matrisen av det mindre elementet.
Del og hersk
Så vi har lært å slå sammen de sortertesamlinger av verdier. Det kan sies at den andre delen av sammenslåingssorteringsalgoritmen - selve sammenslåingen - allerede er sortert.
Du må imidlertid fortsatt forstå hvordan du kommer fra den opprinnelige usorterte tallserien til flere sorterte tall som kan slås sammen.
La oss vurdere den første fasen av algoritmen og lære å skille arrays.
Dette er ikke vanskelig - den opprinnelige verdilisten er delt i to, deretter er hver del også todelt, og så videre til svært små blokker er oppnådd.
Lengden på slike minimale elementer kan være lik én, det vil si at de selv kan være en sortert matrise, men dette er ikke en nødvendig betingelse. Størrelsen på blokken bestemmes på forhånd, og enhver passende sorteringsalgoritme som fungerer effektivt med arrays av små størrelser (for eksempel quicksort eller innsettingssortering) kan brukes til å bestille den.
Det ser slik ut.
// original matrise {34, 95, 10, 2, 102, 70}; // første del {34, 95, 10} og {2, 102, 70}; // andre del {34} og {95, 10} og {2} og {102, 70}
De resulterende blokkene, bestående av 1-2 elementer, er veldig enkle å ordne.
Etter det må du slå sammen de allerede sorterte små arrayene i par, og bevare rekkefølgen på medlemmene, noe vi allerede har lært å gjøre.
Implementering av første trinn
Rekursiv partisjonering av en matrise vises nedenfor.
void mergeSort(T a, lang start, lang avslutning) { long split; hvis(start < mål) { delt=(start + mål)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); slå sammen(a, start, splitt, fullfør); } }
Hva skjer i denne koden:
-
MergeSort-funksjonen får den innledende matrisen
a
og venstre og høyre kant av regionen som skal sorteres (indekser starter og
- finish).
-
Hvis lengden på denne delen er større enn én (
start < finish
), deles den i to deler (etter indeks
- split), og hver enkelt er rekursivt sortert.
-
I det rekursive funksjonsoppkallet for venstre side passeres startindeksen til plottet og indeksen
split
. For den høyre, henholdsvis, vil begynnelsen være
- (splitt + 1), og slutten vil være den siste indeksen til den opprinnelige delen.
-
Function
merge
får to ordnede sekvenser (
a[start]…a[split]
og
- a[split] +1]…a[fullfør]) og slå dem sammen i sorteringsrekkefølge.
Mekanikken til flettefunksjonen er diskutert ovenfor.
Generelt oppsett for algoritmen
Sorteringsmetoden for sammenslåing består av to store trinn:
- Del den usorterte originale matrisen i små biter.
- Samle dem i par, følg sorteringsregelen.
En stor og kompleks oppgave er delt opp i mange enkle, som løses sekvensielt, og fører til ønsket resultat.
Metodevaluering
Tidskompleksiteten til sammenslåingssortering bestemmes av høyden på det delte treetalgoritme og er lik antall elementer i matrisen (n) ganger dens logaritme (log n). Et slikt estimat kalles logaritmisk.
Dette er både en fordel og en ulempe med metoden. Driftstiden endres ikke selv i verste fall, når den opprinnelige matrisen er sortert i omvendt rekkefølge. Men når du behandler fullstendig sorterte data, gir ikke algoritmen noen tidsgevinst.
Det er også viktig å merke seg minnekostnaden ved sammenslåingssorteringsmetoden. De er lik størrelsen på den originale samlingen. I dette tilleggstildelte området blir en sortert matrise satt sammen av brikkene.
Implementering av algoritmen
Pascal-sammenslåingssortering vises nedenfor.
Procedure MergeSort(navn: streng; var f: tekst); Var a1, a2, s, i, j, kol, tmp: heltall; f1, f2: tekst; b: boolsk Startcol:=0; Tilordne(f, navn); tilbakestill(f); Selv om det ikke er EOF(f), begynner read(f, a1); inc(col); slutt; lukke(f); Assign(f1, '{navn på 1. hjelpefil}'); Assign(f2, '{navn på 2. hjelpefil}'); s:=1; Mens (s<kol) begynner Tilbakestill(f); omskriv(f1); omskriv(f2); For i:=1 til kol div 2 begynner Read(f, a1); Skriv(f1, a1, ' '); slutt; Hvis (kol div 2) mod s0 begynner tmp:=kol div 2; Mens tmp mod s0 begynner Read(f, a1); Skriv(f1, a1, ' '); inc(tmp); slutt; slutt; Selv om det ikke er EOF(f), begynner Read(f, a2); Skriv(f2, a2, ' '); slutt; lukke(f); lukk(f1); lukk(f2); omskriv(f); tilbakestill(f1); reset(f2); Les(f1, a1); Les(f2, a2); Mens (ikke EOF(f1)) og (ikke EOF(f2)) begynner i:=0; j:=0; b:=sant; Mens (b) og (ikke EOF(f1)) og (ikke EOF(f2)) begynner If (a1<a2), så begynnerSkriv(f, a1, ' '); Les(f1, a1); inc(i); End else begin Write(f, a2, ' '); Les(f2, a2); inc(j); slutt; Hvis (i=s) eller (j=s) så b:=false; slutt; Hvis ikke b, så begynner While (i<s) og (ikke EOF(f1)) Skriv(f, a1, ' '); Les(f1, a1); inc(i); slutt; Mens (j<s) og (ikke EOF(f2)) begynner Write(f, a2, ' '); Les(f2, a2); inc(j); slutt; slutt; slutt; Selv om det ikke er EOF(f1), begynner tmp:=a1; Les(f1, a1); Hvis ikke EOF(f1) så Skriv(f, tmp, ' ') ellers Skriv(f, tmp); slutt; Selv om det ikke er EOF(f2), begynner tmp:=a2; Les(f2, a2); Hvis ikke EOF(f2) så Skriv(f, tmp, ' ') ellers Skriv(f, tmp); slutt; lukke(f); lukk(f1); lukk(f2); s:=s2; slutt; Slett(f1); Slett(f2); Slutt;
Visuelt ser operasjonen til algoritmen slik ut (øverst - uordnet sekvens, bunn - ordnet).
Ekstern datasortering
Svært ofte er det behov for å sortere noen data som ligger i datamaskinens eksterne minne. I noen tilfeller er de av imponerende størrelse og kan ikke plasseres i RAM for å lette tilgangen til dem. For slike tilfeller brukes eksterne sorteringsmetoder.
Behovet for å få tilgang til eksterne medier reduserer behandlingstidseffektiviteten.
Kompleksiteten i arbeidet er at algoritmen bare kan få tilgang til ett element av datastrømmen om gangen. Og i dette tilfellet vises et av de beste resultatene ved sammenslåingssorteringsmetoden, som kan sammenligne elementene i to filer sekvensielt etter hverandre.
Leser data fraekstern kilde, deres behandling og skriving til den endelige filen utføres i ordnede blokker (serier). Etter måten å jobbe på med størrelse på bestilte serier er det to typer sortering: enkel og naturlig sammenslåing.
Enkel sammenslåing
Med en enkel sammenslåing er serielengden fast.
I den originale usorterte filen består altså alle serier av ett element. Etter det første trinnet øker størrelsen til to. Neste - 4, 8, 16 og så videre.
Det fungerer slik:
- Kildefilen (f) er delt inn i to hjelpefiler - f1, f2.
- De blir igjen slått sammen til én fil (f), men samtidig sammenlignes alle elementer i par og danner par. Seriestørrelsen på dette trinnet blir to.
- Trinn 1 gjentas.
- Trinn 2 gjentas, men de allerede bestilte 2-ene slås sammen til sorterte 4-er.
- Sløyfen fortsetter, og øker serien for hver iterasjon, til hele filen er sortert.
Hvordan vet du at den ytre sorteringen med en enkel sammenslåing er fullført?
- ny serielengde (etter sammenslåing) ikke mindre enn det totale antallet elementer;
- kun én episode igjen;
- Hjelpefil f2 ble stående tom.
Ulempene med en enkel sammenslåing er: siden kjøringslengden er fastsatt ved hvert sammenslåingspass, vil delordnede data ta like lang tid å behandle som helt tilfeldige data.
Naturlig fusjon
Denne metoden begrenser ikke lengdenserie, men velger maksim alt mulig.
Sorteringsalgoritme:
- Leser startsekvensen fra fil f. Det første mottatte elementet skrives til filen f1.
- Hvis neste oppføring tilfredsstiller sorteringsbetingelsen, skrives den der, hvis ikke, så til den andre hjelpefilen f2.
- På denne måten blir alle poster i kildefilen distribuert, og det dannes en ordnet sekvens i f1, som bestemmer gjeldende størrelse på serien.
- Filene f1 og f2 er slått sammen.
- Syklusen gjentas.
På grunn av den ikke-faste størrelsen på serien, er det nødvendig å merke slutten av sekvensen med et spesi altegn. Derfor, ved sammenslåing, øker antallet sammenligninger. I tillegg kan størrelsen på en av hjelpefilene være nær størrelsen på originalen.
I gjennomsnitt er naturlig sammenslåing mer effektiv enn enkel sammenslåing med ekstern sortering.
Funksjoner ved algoritmen
Når man sammenligner to identiske verdier, beholder metoden deres opprinnelige rekkefølge, det vil si at den er stabil.
Sorteringsprosessen kan deles opp i flere tråder med stor suksess.
Videoen demonstrerer tydelig funksjonen til sammenslåingssorteringsalgoritmen.
