Merge sort är en av de grundläggande datavetenskapliga algoritmerna, formulerade redan 1945 av den store matematikern John von Neumann. När Neumann deltog i Manhattan-projektet ställdes han inför behovet av att effektivt bearbeta enorma mängder data. Metoden han utvecklade använde principen om "dela och härska", vilket avsevärt minskade den tid som krävs för arbete.
Princip och användning av algoritmen
Sorteringsmetoden för sammanfogning används i problem med att sortera strukturer som har beordrat åtkomst till element, såsom arrayer, listor, strömmar.
Under bearbetningen delas det initiala datablocket upp i små komponenter, upp till ett element, som faktiskt redan är en sorterad lista. Sedan sätts den ihop i rätt ordning.
Sortering av en array av en viss längd kräver ytterligare ett minnesområde av samma storlek, i vilket den sorterade arrayen är samlad i delar.
Metoden kan användas för att beställa alla jämförbara datatyper, såsom siffror eller strängar.
Sammanfoga sorteradtomter
För att förstå algoritmen, låt oss börja analysen från slutet - från mekanismen för att slå samman sorterade block.
Låt oss föreställa oss att vi har två matriser med nummer sorterade på något sätt som måste kombineras med varandra så att sorteringen inte bryts. För enkelhetens skull kommer vi att sortera siffrorna i stigande ordning.
Elementärt exempel: båda arrayerna består av ett element vardera.
int arr1={31}; int arr2={18};
För att slå samman dem måste du ta nollelementet i den första matrisen (glöm inte att numreringen börjar från noll) och nollelementet i den andra matrisen. Dessa är 31 respektive 18. Enligt sorteringsvillkoret ska siffran 18 komma först, eftersom det är mindre. Sätt bara siffrorna i rätt ordning:
int resultat={18, 31};
Låt oss titta på ett mer komplicerat exempel, där varje array består av flera element:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Sammanfogningsalgoritmen kommer att bestå av att sekventiellt jämföra mindre element och placera dem i den resulterande arrayen i rätt ordning. För att hålla reda på de aktuella indexen, låt oss introducera två variabler - index1 och index2. Till att börja med satte vi dem till noll, eftersom arrayerna är sorterade och de minsta elementen är i början.
int index1=0; int index2=0;
Låt oss skriva hela sammanslagningsprocessen steg för steg:
- Ta elementet med index1 från arrayen arr1 och elementet med index2 från arrayen arr2.
- Jämför, välj den minsta av dem och lägg inresulterande array.
- Öka det aktuella indexet för det mindre elementet med 1.
- Fortsätt från första steget.
På den första omloppsbanan kommer situationen att se ut så här:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; resultat[0]=arr1[0]; // resultat=[2]
På andra svängen:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; resultat[1]=arr2[0]; // resultat=[2, 5]
Tredje:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; resultat[2]=arr2[1]; // resultat=[2, 5, 6]
Och så vidare, tills resultatet är en helt sorterad array: {2, 5, 6, 17, 21, 19, 30, 45}.
Vissa svårigheter kan uppstå om arrayer med olika längder slås samman. Vad händer om ett av de aktuella indexen har nått det sista elementet och det fortfarande finns medlemmar kvar i den andra arrayen?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 steg index1=0, index2=0; 1 2 resultat={1, 2}; // 3-stegs index1=1, index2=1; 4 < 5 resultat={1, 2, 4}; //4 steg index1=2, index2=1 ??
Variabeln index1 har nått värdet 2, men arr1-matrisen har inget element med det indexet. Allt är enkelt här: överför bara de återstående elementen i den andra arrayen till den resulterande, och behåll deras ordning.
resultat={1, 2, 4, 5, 6, 7, 9};
Den här situationen indikerar för oss behovetmatcha det aktuella kontrollindexet med längden på arrayen som slås samman.
Sammanfogningsschema för ordnade sekvenser (A och B) av olika längder:
- Om längden på båda sekvenserna är större än 0, jämför A[0] och B[0] och flytta den mindre till bufferten.
- Om längden på en av sekvenserna är 0, ta de återstående elementen i den andra sekvensen och, utan att ändra deras ordning, flytta till slutet av bufferten.
Implementering av den andra etappen
Ett exempel på att sammanfoga två sorterade arrayer i Java ges nedan.
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; för (int k=0; k al.längd-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++; } annat { int b=a2[j]; a3[k]=b; j++; } }
Här:
- a1 och a2 är de ursprungliga sorterade arrayerna som ska slås samman;
- a3 – final array;
- i och j är index för aktuella element för matriserna a1 och a2.
De första och andra om-villkoren säkerställer att indexen inte går utöver storleken på arrayen. De tredje respektive fjärde villkorsblocken flyttas till den resulterande arrayen av det mindre elementet.
Dela och erövra
Så vi har lärt oss att slå samman de sorteradesamlingar av värden. Man kan säga att den andra delen av sammanslagningssorteringsalgoritmen - själva sammanslagningen - redan har sorterats.
Du behöver dock fortfarande förstå hur du går från den ursprungliga osorterade arrayen av nummer till flera sorterade som kan slås samman.
Låt oss överväga det första steget av algoritmen och lära oss hur man separerar arrayer.
Detta är inte svårt - den ursprungliga värdelistan delas i hälften, sedan är varje del också tvådelad, och så vidare tills mycket små block erhålls.
Längden på sådana minimala element kan vara lika med ett, det vill säga de kan själva vara en sorterad array, men detta är inte ett nödvändigt villkor. Storleken på blocket bestäms i förväg och valfri lämplig sorteringsalgoritm som fungerar effektivt med arrayer av små storlekar (till exempel quicksort eller infogningssortering) kan användas för att beställa det.
Det ser ut så här.
// originalmatris {34, 95, 10, 2, 102, 70}; // första split {34, 95, 10} och {2, 102, 70}; // andra del {34} och {95, 10} och {2} och {102, 70}
De resulterande blocken, bestående av 1-2 element, är mycket enkla att arrangera.
Därefter måste du slå samman de redan sorterade små arrayerna i par, och bevara ordningen på medlemmarna, vilket vi redan har lärt oss att göra.
Implementering av den första etappen
Rekursiv partitionering av en array visas nedan.
void mergeSort(T a, long start, long finish) { long split; om(start < mål) { split=(start + mål)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); merge(a, start, split, finish); } }
Vad händer i den här koden:
-
Funktionen MergeSort får den initiala matrisen
a
och de vänstra och högra gränserna för regionen som ska sorteras (index startar och
- finish).
-
Om längden på det här avsnittet är längre än ett (
start < finish
), delas det i två delar (efter index
- split), och var och en är rekursivt sorterad.
-
I det rekursiva funktionsanropet för vänster sida passeras startindexet för plotten och indexet
split
. För den högra, respektive, kommer början att vara
- (split + 1), och slutet kommer att vara det sista indexet i det ursprungliga avsnittet.
-
Function
merge
får två ordnade sekvenser (
a[start]…a[split]
och
- a[split] +1]…a[avsluta]) och slå samman dem i sorteringsordning.
Mekaniken för sammanslagningsfunktionen diskuteras ovan.
Allmänt schema för algoritmen
Sorteringsmetoden för sammanslagning består av två stora steg:
- Dela den osorterade originaluppsättningen i små bitar.
- Samla dem i par, enligt sorteringsregeln.
En stor och komplex uppgift är uppdelad i många enkla, som löses sekventiellt, vilket leder till önskat resultat.
Metodutvärdering
Tidskomplexiteten för sammanslagningssortering bestäms av höjden på det delade trädetalgoritm och är lika med antalet element i arrayen (n) gånger dess logaritm (log n). En sådan uppskattning kallas logaritmisk.
Detta är både en fördel och en nackdel med metoden. Dess körtid ändras inte ens i värsta fall, när den ursprungliga arrayen sorteras i omvänd ordning. Men vid bearbetning av helt sorterade data ger algoritmen ingen tidsvinst.
Det är också viktigt att notera minneskostnaden för metoden för sammanslagning. De är lika med storleken på originalsamlingen. I detta ytterligare tilldelade område sätts en sorterad array samman från bitarna.
Implementering av algoritmen
Pascal sammanslagningssortering visas nedan.
Procedure MergeSort(namn: sträng; var f: text); Var al, a2, s, i, j, kol, tmp: heltal; f1, f2: text; b: booleskt Börjankol:=0; Tilldela(f, namn); återställ(f); Även om det inte är EOF(f) börjar read(f, a1); inc(kol); slutet; nära(f); Tilldela(f1, '{namn på den första hjälpfilen}'); Assign(f2, '{namn på 2:a hjälpfilen}'); s:=1; Medan (s<kol) börjar Reset(f); skriva om(f1); skriva om(f2); För i:=1 till kol div 2 börjar Read(f, a1); Skriv(f1, a1, ' '); slutet; Om (kol div 2) mod s0 börja då tmp:=kol div 2; Medan tmp mod s0 börjar Read(f, a1); Skriv(f1, a1, ' '); inc(tmp); slutet; slutet; Även om det inte är EOF(f) börjar Read(f, a2); Skriv(f2, a2, ' '); slutet; nära(f); nära(f1); close(f2); skriva om(f); reset(f1); reset(f2); Läs(f1, a1); Läs(f2, a2); Medan (inte EOF(f1)) och (inte EOF(f2)) börjar i:=0; j:=0; b:=sant; Medan (b) och (inte EOF(f1)) och (inte EOF(f2)) börjar If (a1<a2) så börjarSkriv(f, a1, ' '); Läs(f1, a1); inc(i); End else begin Write(f, a2, ' '); Läs(f2, a2); inc(j); slutet; Om (i=s) eller (j=s) då b:=falskt; slutet; Om inte b så börjar While (i<s) och (inte EOF(f1)) Skriv(f, a1, ' '); Läs(f1, a1); inc(i); slutet; Medan (j<s) och (inte EOF(f2)) börjar Write(f, a2, ' '); Läs(f2, a2); inc(j); slutet; slutet; slutet; Även om det inte är EOF(f1) börjar tmp:=a1; Läs(f1, a1); Om inte EOF(f1) så Skriv(f, tmp, ' ') annars Write(f, tmp); slutet; Även om det inte är EOF(f2) börjar tmp:=a2; Läs(f2, a2); Om inte EOF(f2) så Skriv(f, tmp, ' ') annars Write(f, tmp); slutet; nära(f); nära(f1); close(f2); s:=s2; slutet; Erase(f1); Erase(f2); Slut;
Visuellt ser operationen av algoritmen ut så här (överst - oordnad sekvens, botten - ordnad).
Extern datasortering
Mycket ofta finns det ett behov av att sortera vissa data som finns i datorns externa minne. I vissa fall är de av imponerande storlek och kan inte placeras i RAM för att underlätta åtkomst till dem. För sådana fall används externa sorteringsmetoder.
Behovet av att få tillgång till externa medier försämrar effektiviteten i behandlingstiden.
Komplexiteten i arbetet är att algoritmen bara kan komma åt en del av dataströmmen åt gången. Och i det här fallet visas ett av de bästa resultaten av metoden för sammanslagningssortering, som kan jämföra elementen i två filer sekventiellt efter varandra.
Läser data frånextern källa, deras bearbetning och skrivning till den slutliga filen utförs i ordnade block (serier). Beroende på hur man arbetar med storleken på beställda serier finns det två sorters sortering: enkel och naturlig sammanslagning.
Enkel sammanslagning
Med en enkel sammanfogning är serielängden fast.
I den ursprungliga osorterade filen består alltså alla serier av ett element. Efter det första steget ökar storleken till två. Nästa - 4, 8, 16 och så vidare.
Det fungerar så här:
- Källfilen (f) är uppdelad i två hjälpfiler - f1, f2.
- De slås åter samman till en fil (f), men samtidigt jämförs alla element i par och bildar par. Seriestorleken i detta steg blir två.
- Steg 1 upprepas.
- Steg 2 upprepas, men de redan beställda 2:orna slås samman till sorterade 4:or.
- Slingan fortsätter och ökar serien för varje iteration tills hela filen är sorterad.
Hur vet du att den yttre sorteringen med en enkel sammanfogning är klar?
- ny serielängd (efter sammanslagning) inte mindre än det totala antalet element;
- bara ett avsnitt kvar;
- Hjälpfil f2 lämnades tom.
Nackdelarna med en enkel sammanfogning är: eftersom körlängden är fixerad vid varje sammanfogningspass, kommer partiellt beställd data att ta lika lång tid att behandla som helt slumpmässig data.
Naturlig fusion
Denna metod begränsar inte längdenserie, men väljer det högsta möjliga.
Sorteringsalgoritm:
- Läser den initiala sekvensen från fil f. Det första mottagna elementet skrivs till filen f1.
- Om nästa post uppfyller sorteringsvillkoret skrivs den där, om inte, sedan till den andra hjälpfilen f2.
- På detta sätt distribueras alla poster i källfilen, och en ordnad sekvens bildas i f1, som bestämmer den aktuella storleken på serien.
- Filer f1 och f2 slås samman.
- Cykeln upprepas.
På grund av den icke-fasta storleken på serien är det nödvändigt att markera slutet av sekvensen med ett speci altecken. Därför ökar antalet jämförelser vid sammanslagning. Dessutom kan storleken på en av hjälpfilerna vara nära storleken på originalet.
I genomsnitt är naturlig sammanslagning effektivare än enkel sammanslagning med extern sortering.
Funktioner i algoritmen
När man jämför två identiska värden behåller metoden sin ursprungliga ordning, det vill säga den är stabil.
Sorteringsprocessen kan mycket framgångsrikt delas upp i flera trådar.
Videon visar tydligt hur sammanslagningssorteringsalgoritmen fungerar.
