Samenvoegen is een van de basisalgoritmen voor informatica, die in 1945 werd geformuleerd door de grote wiskundige John von Neumann. Tijdens zijn deelname aan het Manhattan-project werd Neumann geconfronteerd met de noodzaak om enorme hoeveelheden gegevens efficiënt te verwerken. De methode die hij ontwikkelde, maakte gebruik van het principe van "verdeel en heers", waardoor de werktijd aanzienlijk werd verkort.
Principe en gebruik van het algoritme
De merge sort-methode wordt gebruikt bij problemen met het sorteren van structuren die toegang tot elementen geordend hebben, zoals arrays, lijsten, streams.
Tijdens de verwerking wordt het initiële gegevensblok opgesplitst in kleine componenten, tot één element, dat in feite al een gesorteerde lijst is. Daarna wordt het in de juiste volgorde weer in elkaar gezet.
Het sorteren van een array van een bepaalde lengte vereist een extra geheugengebied van dezelfde grootte, waarin de gesorteerde array in delen wordt verzameld.
De methode kan worden gebruikt om elk vergelijkbaar gegevenstype te bestellen, zoals getallen of tekenreeksen.
Samenvoegen gesorteerdpercelen
Om het algoritme te begrijpen, laten we de analyse vanaf het einde beginnen - vanaf het mechanisme van het samenvoegen van gesorteerde blokken.
Laten we ons voorstellen dat we twee reeksen getallen hebben die op welke manier dan ook zijn gesorteerd en die met elkaar moeten worden gecombineerd, zodat de sortering niet wordt verbroken. Voor de eenvoud sorteren we de getallen in oplopende volgorde.
Elementair voorbeeld: beide arrays bestaan elk uit één element.
int arr1={31}; int arr2={18};
Om ze samen te voegen, moet je het nul-element van de eerste array nemen (vergeet niet dat de nummering begint bij nul) en het nul-element van de tweede array. Dit zijn respectievelijk 31 en 18. Volgens de sorteerconditie moet het getal 18 eerst komen, omdat het minder is. Zet de cijfers gewoon in de juiste volgorde:
int resultaat={18, 31};
Laten we een ingewikkelder voorbeeld bekijken, waarbij elke array uit verschillende elementen bestaat:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Het samenvoegalgoritme zal bestaan uit het achtereenvolgens vergelijken van kleinere elementen en deze in de juiste volgorde in de resulterende array te plaatsen. Om de huidige indices bij te houden, introduceren we twee variabelen - index1 en index2. Aanvankelijk stellen we ze op nul, omdat de arrays zijn gesorteerd en de kleinste elementen aan het begin staan.
int index1=0; int index2=0;
Laten we het hele samenvoegproces stap voor stap opschrijven:
- Neem het element met index1 uit de array arr1, en het element met index2 uit de array arr2.
- Vergelijk, selecteer de kleinste en zet inresulterende array.
- Verhoog de huidige index van het kleinere element met 1.
- Doorgaan vanaf de eerste stap.
In de eerste baan ziet de situatie er als volgt uit:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; resultaat[0]=arr1[0]; // resultaat=[2]
Bij de tweede afslag:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; resultaat[1]=arr2[0]; // resultaat=[2, 5]
Derde:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; resultaat[2]=arr2[1]; // resultaat=[2, 5, 6]
En zo verder, totdat het resultaat een volledig gesorteerde array is: {2, 5, 6, 17, 21, 19, 30, 45}.
Er kunnen zich bepaalde problemen voordoen als arrays met verschillende lengtes worden samengevoegd. Wat als een van de huidige indexen het laatste element heeft bereikt en er zijn nog leden over in de tweede array?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 stap index1=0, index2=0; 1 2 resultaat={1, 2}; // 3-staps index1=1, index2=1; 4 < 5 resultaat={1, 2, 4}; //4 stap index1=2, index2=1 ??
De variabele index1 heeft de waarde 2 bereikt, maar de array arr1 heeft geen element met die index. Alles is hier eenvoudig: breng gewoon de resterende elementen van de tweede array over naar de resulterende, met behoud van hun volgorde.
resultaat={1, 2, 4, 5, 6, 7, 9};
Deze situatie geeft ons de noodzaak aanmatch de huidige controle-index met de lengte van de array die wordt samengevoegd.
Samenvoegschema voor geordende reeksen (A en B) van verschillende lengtes:
- Als de lengte van beide reeksen groter is dan 0, vergelijk A[0] en B[0] en verplaats de kleinere naar de buffer.
- Als de lengte van een van de reeksen 0 is, neem dan de resterende elementen van de tweede reeks en ga, zonder hun volgorde te veranderen, naar het einde van de buffer.
Implementatie van de tweede fase
Een voorbeeld van het samenvoegen van twee gesorteerde arrays in Java wordt hieronder gegeven.
int a1=nieuwe int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nieuw int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nieuw int[a1.length + a2.length]; int i=0, j=0; voor (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=een; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=een; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=een; i++; } anders { int b=a2[j]; a3[k]=b; j++; } }
Hier:
- a1 en a2 zijn de originele gesorteerde arrays die moeten worden samengevoegd;
- a3 – laatste array;
- i en j zijn indexen van huidige elementen voor arrays a1 en a2.
De eerste en tweede if-voorwaarden zorgen ervoor dat de indexen niet verder gaan dan de grootte van de array. De derde en vierde voorwaardeblokken worden respectievelijk verplaatst naar de resulterende array van het kleinere element.
Verdeel en heers
Dus, we hebben geleerd om de gesorteerde samen te voegenverzamelingen van waarden. Het kan worden gezegd dat het tweede deel van het samenvoeg-sorteeralgoritme - de samenvoeging zelf - al is gesorteerd.
U moet echter nog steeds begrijpen hoe u van de oorspronkelijke ongesorteerde reeks getallen naar verschillende gesorteerde getallen kunt komen die kunnen worden samengevoegd.
Laten we de eerste fase van het algoritme eens bekijken en leren hoe arrays te scheiden.
Dit is niet moeilijk - de originele lijst met waarden wordt in tweeën gedeeld, vervolgens wordt elk deel ook gesplitst, enzovoort totdat er zeer kleine blokken worden verkregen.
De lengte van zulke minimale elementen kan gelijk zijn aan één, dat wil zeggen dat ze zelf een gesorteerde array kunnen zijn, maar dit is geen noodzakelijke voorwaarde. De grootte van het blok wordt vooraf bepaald en elk geschikt sorteeralgoritme dat efficiënt werkt met arrays van kleine afmetingen (bijvoorbeeld quicksort of insertion sort) kan worden gebruikt om het te bestellen.
Het ziet er zo uit.
// originele array {34, 95, 10, 2, 102, 70}; // eerste splitsing {34, 95, 10} en {2, 102, 70}; // tweede splitsing {34} en {95, 10} en {2} en {102, 70}
De resulterende blokken, bestaande uit 1-2 elementen, zijn heel gemakkelijk te rangschikken.
Daarna moet je de reeds gesorteerde kleine arrays in paren samenvoegen, waarbij de volgorde van de leden behouden blijft, wat we al hebben geleerd om te doen.
Implementatie van de eerste fase
Recursieve partitionering van een array wordt hieronder getoond.
void mergeSort(T a, long start, long finish) { long split; indien(start < finish) { split=(start + finish)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); samenvoegen (a, start, split, finish); } }
Wat gebeurt er in deze code:
-
De mergeSort-functie ha alt de initiële array
a
en de linker- en rechterranden van het te sorteren gebied op (indices start en
- finish).
-
Als de lengte van dit gedeelte groter is dan één (
start < finish
), dan wordt het in twee delen gesplitst (volgens index
- split), en elk wordt recursief gesorteerd.
-
In de recursieve functieaanroep voor de linkerkant worden de startindex van de plot en de index
split
doorgegeven. Voor de rechter is het begin respectievelijk
- (split + 1), en het einde is de laatste index van de originele sectie.
-
Functie
merge
krijgt twee geordende reeksen (
a[start]…a[split]
en
- a[split +1]…a[finish]) en voegt ze samen in sorteervolgorde.
De mechanica van de samenvoegfunctie wordt hierboven besproken.
Algemeen schema van het algoritme
De merge sort array-methode bestaat uit twee grote stappen:
- Verdeel de ongesorteerde originele array in kleine stukjes.
- Verzamel ze in paren volgens de sorteerregel.
Een grote en complexe taak wordt opgesplitst in vele eenvoudige, die achtereenvolgens worden opgelost, wat leidt tot het gewenste resultaat.
Methode evaluatie
De tijdscomplexiteit van samenvoegsortering wordt bepaald door de hoogte van de gesplitste boomalgoritme en is gelijk aan het aantal elementen in de array (n) maal de logaritme (log n). Zo'n schatting wordt logaritmisch genoemd.
Dit is zowel een voordeel als een nadeel van de methode. De looptijd verandert niet, zelfs niet in het ergste geval, wanneer de originele array in omgekeerde volgorde wordt gesorteerd. Bij het verwerken van volledig gesorteerde gegevens levert het algoritme echter geen tijdwinst op.
Het is ook belangrijk om de geheugenkosten van de samenvoegsorteermethode te noteren. Ze zijn even groot als de originele collectie. In dit extra toegewezen gebied wordt een gesorteerde reeks samengesteld uit de stukken.
Implementatie van het algoritme
Pascal merge sort wordt hieronder getoond.
Procedure MergeSort(naam: string; var f: tekst); Var a1, a2, s, i, j, kol, tmp: geheel getal; f1, f2: tekst; b: booleaans Begincol:=0; Toewijzen (f, naam); reset(f); Hoewel EOF(f) niet begint met lezen (f, a1); inc(col); einde; sluiten (v); Assign(f1, '{naam van 1e hulpbestand}'); Assign(f2, '{naam van 2e hulpbestand}'); s:=1; Terwijl (s<kol) Reset(f) wel begint; herschrijven (f1); herschrijven (f2); Voor i:=1 tot kol div 2 begin Read(f, a1); Schrijf(f1, a1, ' '); einde; Als (kol div 2) mod s0 begin dan met tmp:=kol div 2; Terwijl tmp mod s0 wel begint met Read(f, a1); Schrijf(f1, a1, ' '); inc(tmp); einde; einde; Hoewel EOF(f) niet begint met Read(f, a2); Schrijf(f2, a2, ' '); einde; sluiten (v); sluiten (f1); sluiten (f2); herschrijven (f); reset(f1); resetten (f2); Lezen (f1, a1); Lezen (f2, a2); Terwijl (niet EOF(f1)) en (niet EOF(f2)) beginnen i:=0; j:=0; b:=waar; Terwijl (b) en (niet EOF(f1)) en (niet EOF(f2)) wel beginnen Als (a1<a2) dan beginnenSchrijf(f, a1, ' '); Lezen (f1, a1); inc(i); Einde anders begin Write(f, a2, ' '); Lezen (f2, a2); inc(j); einde; Als (i=s) of (j=s) dan b:=false; einde; Zo niet b, begin While (i<s) en (niet EOF(f1)) wel met Write(f, a1, ' '); Lezen (f1, a1); inc(i); einde; Terwijl (j<s) en (niet EOF(f2)) Write(f, a2, ' '); Lezen (f2, a2); inc(j); einde; einde; einde; Hoewel niet EOF(f1) begint tmp:=a1; Lezen (f1, a1); Indien niet EOF(f1) dan Write(f, tmp, ' ') else Write(f, tmp); einde; Hoewel niet EOF(f2) begint tmp:=a2; Lezen (f2, a2); Indien niet EOF(f2) dan Write(f, tmp, ' ') else Write(f, tmp); einde; sluiten (v); sluiten (f1); sluiten (f2); s:=s2; einde; Wissen (f1); Wissen (f2); Einde;
Visueel ziet de werking van het algoritme er als volgt uit (boven - ongeordende reeks, onder - geordend).
Externe gegevens sorteren
Heel vaak is het nodig om bepaalde gegevens in het externe geheugen van de computer te sorteren. In sommige gevallen zijn ze indrukwekkend groot en kunnen ze niet in het RAM worden geplaatst om de toegang ertoe te vergemakkelijken. Voor dergelijke gevallen worden externe sorteermethoden gebruikt.
De noodzaak om toegang te krijgen tot externe media verslechtert de efficiëntie van de verwerkingstijd.
De complexiteit van het werk is dat het algoritme slechts toegang heeft tot één element van de gegevensstroom tegelijk. En in dit geval wordt een van de beste resultaten getoond door de merge sort-methode, die de elementen van twee bestanden achter elkaar kan vergelijken.
Gegevens lezen vanexterne bron, hun verwerking en schrijven naar het uiteindelijke bestand worden uitgevoerd in geordende blokken (reeksen). Volgens de manier van werken met de grootte van geordende series zijn er twee soorten sortering: eenvoudig en natuurlijk samenvoegen.
Eenvoudig samenvoegen
Met een simpele samenvoeging ligt de lengte van de reeks vast.
In het originele ongesorteerde bestand bestaan dus alle series uit één element. Na de eerste stap neemt de maat toe tot twee. Volgende - 4, 8, 16 enzovoort.
Het werkt als volgt:
- Het bronbestand (f) is verdeeld in twee hulpbestanden - f1, f2.
- Ze worden weer samengevoegd tot één bestand (f), maar tegelijkertijd worden alle elementen in paren vergeleken en vormen paren. De seriegrootte bij deze stap wordt twee.
- Stap 1 wordt herhaald.
- Stap 2 wordt herhaald, maar de reeds geordende 2's worden samengevoegd tot gesorteerde 4's.
- De lus gaat verder, waarbij de reeks bij elke iteratie toeneemt, totdat het hele bestand is gesorteerd.
Hoe weet je dat de buitenste sortering met een simpele samenvoeging voltooid is?
- nieuwe reekslengte (na samenvoegen) niet minder dan het totale aantal elementen;
- nog maar één aflevering over;
- Hulpbestand f2 is leeg gelaten.
De nadelen van een eenvoudige samenvoeging zijn: aangezien de runlengte bij elke samenvoeggang vastligt, duurt het verwerken van gedeeltelijk geordende gegevens net zo lang als volledig willekeurige gegevens.
Natuurlijke fusie
Deze methode beperkt de lengte nietserie, maar kiest het maximaal mogelijke.
Sorteeralgoritme:
- Lezen van de eerste reeks uit bestand f. Het eerste ontvangen element wordt weggeschreven naar het bestand f1.
- Als het volgende item voldoet aan de sorteervoorwaarde, wordt het daar weggeschreven, zo niet, dan naar het tweede hulpbestand f2.
- Op deze manier worden alle records van het bronbestand gedistribueerd en wordt een geordende reeks gevormd in f1, die de huidige grootte van de reeks bepa alt.
- Bestanden f1 en f2 zijn samengevoegd.
- De cyclus herha alt zich.
Vanwege de niet-vaste grootte van de reeks, is het noodzakelijk om het einde van de reeks te markeren met een speciaal teken. Daarom neemt bij het samenvoegen het aantal vergelijkingen toe. Bovendien kan de grootte van een van de hulpbestanden dicht bij de grootte van het origineel liggen.
Natuurlijk samenvoegen is gemiddeld efficiënter dan eenvoudig samenvoegen met externe sortering.
Kenmerken van het algoritme
Bij het vergelijken van twee identieke waarden behoudt de methode hun oorspronkelijke volgorde, dat wil zeggen, het is stabiel.
Het sorteerproces kan zeer succesvol worden opgesplitst in meerdere threads.
De video demonstreert duidelijk de werking van het sorteeralgoritme voor samenvoegen.
