Merge sort er en af de grundlæggende datalogiske algoritmer, formuleret tilbage i 1945 af den store matematiker John von Neumann. Mens han deltog i Manhattan-projektet, stod Neumann over for behovet for effektivt at behandle enorme mængder data. Metoden, han udviklede, brugte princippet om "del og hersk", hvilket reducerede den tid, der krævedes til arbejdet, markant.
Princip og brug af algoritmen
Fletsorteringsmetoden bruges i problemer med sortering af strukturer, der har bestilt adgang til elementer, såsom arrays, lister, streams.
Under behandlingen opdeles den indledende datablok i små komponenter, op til ét element, som faktisk allerede er en sorteret liste. Derefter samles det igen i den rigtige rækkefølge.
Sortering af et array af en vis længde kræver et ekstra hukommelsesområde af samme størrelse, hvor det sorterede array er samlet i dele.
Metoden kan bruges til at bestille enhver sammenlignelig datatype, såsom tal eller strenge.
Flet sorteretplots
For at forstå algoritmen, lad os starte analysen fra slutningen - fra mekanismen til at flette sorterede blokke.
Lad os forestille os, at vi har to rækker af tal sorteret på en hvilken som helst måde, som skal kombineres med hinanden, så sorteringen ikke brydes. For nemheds skyld sorterer vi tallene i stigende rækkefølge.
Elementært eksempel: begge arrays består af et element hver.
int arr1={31}; int arr2={18};
For at flette dem skal du tage nul-elementet i det første array (glem ikke, at nummereringen starter fra nul) og nul-elementet i det andet array. Disse er henholdsvis 31 og 18. Ifølge sorteringsbetingelsen skal tallet 18 komme først, da det er mindre. Sæt bare tallene i den rigtige rækkefølge:
int resultat={18, 31};
Lad os se på et mere kompliceret eksempel, hvor hvert array består af flere elementer:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Fletningsalgoritmen vil bestå af sekventielt at sammenligne mindre elementer og placere dem i det resulterende array i den rigtige rækkefølge. For at holde styr på de aktuelle indekser, lad os introducere to variable - indeks1 og indeks2. Til at begynde med satte vi dem til nul, da arrays er sorteret, og de mindste elementer er i begyndelsen.
int index1=0; int index2=0;
Lad os skrive hele sammenlægningsprocessen trin for trin:
- Tag elementet med index1 fra arrayet arr1, og elementet med index2 fra arrayet arr2.
- Sammenlign, vælg den mindste af dem og indsætresulterende matrix.
- Forøg det aktuelle indeks for det mindre element med 1.
- Fortsæt fra første trin.
På den første bane vil situationen se sådan ud:
index1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; resultat[0]=arr1[0]; // resultat=[2]
På anden omgang:
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, indtil resultatet er en fuldstændig sorteret matrix: {2, 5, 6, 17, 21, 19, 30, 45}.
Der kan opstå visse vanskeligheder, hvis arrays med forskellige længder slås sammen. Hvad hvis et af de aktuelle indekser har nået det sidste element, og der stadig er medlemmer tilbage i det andet array?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 trin indeks1=0, indeks2=0; 1 2 resultat={1, 2}; // 3-trins indeks1=1, indeks2=1; 4 < 5 resultat={1, 2, 4}; //4-trins indeks1=2, indeks2=1 ??
Indeks1-variablen har nået værdien 2, men arr1-arrayet har ikke et element med det indeks. Alt er enkelt her: Overfør blot de resterende elementer i den anden matrix til den resulterende, og bevar deres rækkefølge.
resultat={1, 2, 4, 5, 6, 7, 9};
Denne situation viser os behovetmatch det aktuelle kontrolindeks med længden af det array, der flettes.
Fletskema for ordnede sekvenser (A og B) af forskellig længde:
- Hvis længden af begge sekvenser er større end 0, skal du sammenligne A[0] og B[0] og flytte den mindste til bufferen.
- Hvis længden af en af sekvenserne er 0, skal du tage de resterende elementer i den anden sekvens og, uden at ændre deres rækkefølge, gå til slutningen af bufferen.
Implementering af anden fase
Et eksempel på at forbinde to sorterede arrays i Java er givet 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=ny int[a1.længde + a2.længde]; int i=0, j=0; for (int k=0; k a1.længde-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++; } andet { int b=a2[j]; a3[k]=b; j++; } }
Her:
- a1 og a2 er de originale sorterede arrays, der skal flettes;
- a3 – endelig array;
- i og j er indekser af aktuelle elementer for arrays a1 og a2.
Den første og anden hvis-betingelser sikrer, at indekserne ikke går ud over størrelsen af arrayet. Den tredje og fjerde betingelsesblok flyttes til det resulterende array af det mindre element.
Del og hersk
Så vi har lært at flette de sorteredesamlinger af værdier. Det kan siges, at den anden del af flettesorteringsalgoritmen - selve fletningen - allerede er blevet sorteret.
Du mangler dog stadig at forstå, hvordan du kommer fra den oprindelige usorterede række af tal til flere sorterede, der kan flettes.
Lad os overveje den første fase af algoritmen og lære, hvordan man adskiller arrays.
Dette er ikke svært - den oprindelige liste over værdier er delt i to, derefter er hver del også todelt, og så videre, indtil der er opnået meget små blokke.
Længden af sådanne minimale elementer kan være lig med én, det vil sige, at de selv kan være et sorteret array, men dette er ikke en nødvendig betingelse. Størrelsen af blokken bestemmes på forhånd, og enhver passende sorteringsalgoritme, der fungerer effektivt med arrays af små størrelser (f.eks. quicksort eller insertion sort), kan bruges til at bestille den.
Det ser sådan ud.
// origin alt array {34, 95, 10, 2, 102, 70}; // første opdeling {34, 95, 10} og {2, 102, 70}; // sekundsplit {34} og {95, 10} og {2} og {102, 70}
De resulterende blokke, der består af 1-2 elementer, er meget nemme at arrangere.
Derefter skal du flette de allerede sorterede små arrays i par og bevare rækkefølgen af medlemmerne, hvilket vi allerede har lært at gøre.
Implementering af den første fase
Rekursiv partitionering af et array er vist nedenfor.
void mergeSort(T a, lang start, lang afslutning) { long split; hvis(start < finish) { split=(start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); flette(a, start, split, finish); } }
Hvad sker der i denne kode:
-
MergeSort-funktionen får den indledende matrix
a
og venstre og højre grænser for regionen, der skal sorteres (indekser starter og
- finish).
-
Hvis længden af denne sektion er større end én (
start < finish
), opdeles den i to dele (efter indeks
- split), og hver enkelt er rekursivt sorteret.
-
I det rekursive funktionskald for venstre side passeres startindekset for plottet og indekset
split
. For henholdsvis den højre vil begyndelsen være
- (split + 1), og slutningen vil være det sidste indeks i den originale sektion.
-
Function
merge
får to ordnede sekvenser (
a[start]…a[split]
og
- a[split] +1]…a[afslut]) og flette dem i sorteringsrækkefølge.
Mekanikken i flettefunktionen er diskuteret ovenfor.
Generelt skema for algoritmen
Fletsorteringsmetoden består af to store trin:
- Opdel det usorterede originale array i små stykker.
- Saml dem i par og følg sorteringsreglen.
En stor og kompleks opgave er opdelt i mange simple, som løses sekventielt, hvilket fører til det ønskede resultat.
Metodevaluering
Tidskompleksiteten af flettesortering bestemmes af højden af det opdelte træalgoritme og er lig med antallet af elementer i arrayet (n) gange dens logaritme (log n). Et sådant estimat kaldes logaritmisk.
Dette er både en fordel og en ulempe ved metoden. Dens køretid ændres ikke, selv i værste tilfælde, når det originale array er sorteret i omvendt rækkefølge. Men når man behandler fuldstændigt sorterede data, giver algoritmen ingen tidsgevinst.
Det er også vigtigt at bemærke hukommelsesomkostningerne ved flettesorteringsmetoden. De er lig med størrelsen af den originale samling. I dette yderligere tildelte område samles et sorteret array fra brikkerne.
Implementering af algoritmen
Pascal-fletningssortering er vist nedenfor.
Procedure MergeSort(navn: streng; var f: tekst); Var a1, a2, s, i, j, kol, tmp: heltal; f1, f2: tekst; b: boolesk Startcol:=0; Tildel(f, navn); nulstil(f); Selvom det ikke er EOF(f), begynder read(f, a1); inc(col); ende; lukke(f); Assign(f1, '{navn på 1. hjælpefil}'); Assign(f2, '{navn på 2. hjælpefil}'); s:=1; Mens (s<kol) begynder Nulstil(f); omskriv(f1); omskriv(f2); For i:=1 til kol div 2 begynder Read(f, a1); Skriv(f1, a1, ' '); ende; Hvis (kol div 2) mod s0, så start tmp:=kol div 2; Mens tmp mod s0 begynder Read(f, a1); Skriv(f1, a1, ' '); inc(tmp); ende; ende; Selvom det ikke er EOF(f), begynder Read(f, a2); Skriv(f2, a2, ' '); ende; lukke(f); lukke(f1); lukke(f2); omskriv(f); nulstil(f1); nulstil(f2); Læs(f1, a1); Læs(f2, a2); Mens (ikke EOF(f1)) og (ikke EOF(f2)) begynder i:=0; j:=0; b:=sandt; Mens (b) og (ikke EOF(f1)) og (ikke EOF(f2)) begynder If (a1<a2), så begynderSkriv(f, a1, ' '); Læs(f1, a1); inc(i); End else begin Write(f, a2, ' '); Læs(f2, a2); inc(j); ende; Hvis (i=s) eller (j=s) så b:=falsk; ende; Hvis ikke b, så begynder While (i<s) og (ikke EOF(f1)) skal skrive(f, a1, ' '); Læs(f1, a1); inc(i); ende; Mens (j<s) og (ikke EOF(f2)) begynder Write(f, a2, ' '); Læs(f2, a2); inc(j); ende; ende; ende; Selvom det ikke er EOF(f1), så begynder tmp:=a1; Læs(f1, a1); Hvis ikke EOF(f1) så Skriv(f, tmp, ' ') ellers Skriv(f, tmp); ende; Selvom det ikke er EOF(f2), begynder tmp:=a2; Læs(f2, a2); Hvis ikke EOF(f2) så Skriv(f, tmp, ' ') ellers Skriv(f, tmp); ende; lukke(f); lukke(f1); lukke(f2); s:=s2; ende; Slet(f1); Slet(f2); Slut;
Visuelt ser operationen af algoritmen sådan ud (øverst - uordnet sekvens, nederst - ordnet).
Ekstern datasortering
Meget ofte er der behov for at sortere nogle data i computerens eksterne hukommelse. I nogle tilfælde er de af imponerende størrelse og kan ikke placeres i RAM for at lette adgangen til dem. I sådanne tilfælde bruges eksterne sorteringsmetoder.
Behovet for at få adgang til eksterne medier forringer behandlingstidseffektiviteten.
Kompleksiteten af arbejdet er, at algoritmen kun kan få adgang til ét element af datastrømmen ad gangen. Og i dette tilfælde vises et af de bedste resultater ved flettesorteringsmetoden, som kan sammenligne elementerne i to filer sekventielt efter hinanden.
Læser data fraekstern kilde, deres behandling og skrivning til den endelige fil udføres i ordnede blokke (serier). Ifølge måden at arbejde med størrelsen på bestilte serier er der to typer sortering: enkel og naturlig sammenlægning.
Simpel fletning
Med en simpel fletning er serielængden fast.
I den originale usorterede fil består alle serier af ét element. Efter det første trin øges størrelsen til to. Næste - 4, 8, 16 og så videre.
Det fungerer sådan her:
- Kildefilen (f) er opdelt i to hjælpefiler - f1, f2.
- De er igen slået sammen til én fil (f), men samtidig sammenlignes alle elementer i par og danner par. Seriestørrelsen på dette trin bliver to.
- Trin 1 gentages.
- Trin 2 gentages, men de allerede bestilte 2'ere slås sammen til sorterede 4'ere.
- Sløjfen fortsætter og øger serien for hver iteration, indtil hele filen er sorteret.
Hvordan ved du, at den ydre sortering med en simpel fletning er fuldført?
- ny serielængde (efter sammenlægning) ikke mindre end det samlede antal elementer;
- kun ét afsnit tilbage;
- Hjælpefil f2 blev efterladt tom.
Ulemperne ved en simpel fletning er: da kørselslængden er fastsat ved hver fletning, vil delvist bestilte data tage lige så lang tid at behandle som fuldstændig tilfældige data.
Naturlig fusion
Denne metode begrænser ikke længdenserie, men vælger det maksim alt mulige.
Sorteringsalgoritme:
- Læsning af den indledende sekvens fra fil f. Det første modtagne element skrives til filen f1.
- Hvis den næste post opfylder sorteringsbetingelsen, skrives den der, hvis ikke, så til den anden hjælpefil f2.
- På denne måde distribueres alle poster i kildefilen, og der dannes en ordnet sekvens i f1, som bestemmer seriens aktuelle størrelse.
- Filer f1 og f2 er flettet.
- Cyklusen gentages.
På grund af seriens ikke-faste størrelse er det nødvendigt at markere slutningen af sekvensen med et speci altegn. Derfor stiger antallet af sammenligninger ved sammenlægning. Derudover kan størrelsen af en af hjælpefilerne være tæt på størrelsen af originalen.
I gennemsnit er naturlig fletning mere effektiv end simpel fletning med ekstern sortering.
Funktioner i algoritmen
Når man sammenligner to identiske værdier, bevarer metoden deres oprindelige rækkefølge, dvs. den er stabil.
Sorteringsprocessen kan med stor succes opdeles i flere tråde.
Videoen demonstrerer tydeligt driften af flettesorteringsalgoritmen.
