Merge sort is een van die basiese rekenaarwetenskapalgoritmes, wat in 1945 deur die groot wiskundige John von Neumann geformuleer is. Terwyl hy aan die Manhattan-projek deelgeneem het, het Neumann gekonfronteer met die behoefte om groot hoeveelhede data doeltreffend te verwerk. Die metode wat hy ontwikkel het, het die beginsel van "verdeel en heers" gebruik, wat die tyd wat nodig is vir werk aansienlik verminder het.
Beginsel en gebruik van die algoritme
Die samesmeltingssorteermetode word gebruik in probleme met sortering van strukture wat toegang tot elemente georden het, soos skikkings, lyste, strome.
Tydens verwerking word die aanvanklike datablok in klein komponente verdeel, tot een element, wat in werklikheid reeds 'n gesorteerde lys is. Dan word dit weer in die regte volgorde aanmekaargesit.
Om 'n skikking van 'n sekere lengte te sorteer, vereis 'n bykomende geheue-area van dieselfde grootte, waarin die gesorteerde skikking in dele versamel word.
Die metode kan gebruik word om enige vergelykbare datatipe te bestel, soos getalle of stringe.
Saamvoeg gesorteererwe
Om die algoritme te verstaan, kom ons begin sy ontleding van die einde af - vanaf die meganisme om gesorteerde blokke saam te voeg.
Kom ons stel ons voor dat ons twee skikkings getalle het wat op enige manier gesorteer is wat met mekaar gekombineer moet word sodat die sortering nie gebreek word nie. Vir eenvoud sal ons die getalle in stygende volgorde sorteer.
Elementêre voorbeeld: beide skikkings bestaan uit een element elk.
int arr1={31}; int arr2={18};
Om hulle saam te voeg, moet jy die nul-element van die eerste skikking neem (moenie vergeet dat nommering vanaf nul begin nie) en die nul-element van die tweede skikking. Dit is onderskeidelik 31 en 18. Volgens die sorteervoorwaarde moet die nommer 18 eerste kom, aangesien dit minder is. Plaas net die nommers in die regte volgorde:
int resultaat={18, 31};
Kom ons kyk na 'n meer ingewikkelde voorbeeld, waar elke skikking uit verskeie elemente bestaan:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Die samesmeltingsalgoritme sal bestaan uit die opeenvolgende vergelyking van kleiner elemente en om hulle in die resulterende skikking in die korrekte volgorde te plaas. Om tred te hou met die huidige indekse, kom ons stel twee veranderlikes bekend – indeks1 en indeks2. Aanvanklik het ons hulle op nul gestel, aangesien die skikkings gesorteer is, en die kleinste elemente aan die begin is.
int indeks1=0; int indeks2=0;
Kom ons skryf die hele samesmeltingsproses stap vir stap:
- Neem die element met indeks1 van die skikking arr1, en die element met indeks2 van die skikking arr2.
- Vergelyk, kies die kleinste van hulle en sit inresulterende skikking.
- Verhoog die huidige indeks van die kleiner element met 1.
- Gaan voort vanaf die eerste stap.
Op die eerste wentelbaan sal die situasie soos volg lyk:
indeks1=0; indeks2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeks1++; resultaat[0]=arr1[0]; // resultaat=[2]
Op die tweede draai:
indeks1=1; indeks2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeks2++; resultaat[1]=arr2[0]; // resultaat=[2, 5]
Derde:
indeks1=1; indeks2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeks2++; resultaat[2]=arr2[1]; // resultaat=[2, 5, 6]
En so aan, totdat die resultaat 'n heeltemal gesorteerde skikking is: {2, 5, 6, 17, 21, 19, 30, 45}.
Sekere probleme kan ontstaan as skikkings met verskillende lengtes saamgevoeg word. Wat as een van die huidige indekse die laaste element bereik het, en daar is nog lede oor in die tweede skikking?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 stap indeks1=0, indeks2=0; 1 2 resultaat={1, 2}; // 3 stap indeks1=1, indeks2=1; 4 < 5 resultaat={1, 2, 4}; //4 stap indeks1=2, indeks2=1 ??
Die indeks1-veranderlike het die waarde 2 bereik, maar die arr1-skikking het nie 'n element met daardie indeks nie. Alles is eenvoudig hier: dra net die oorblywende elemente van die tweede skikking oor na die resulterende een, en behou hul volgorde.
resultaat={1, 2, 4, 5, 6, 7, 9};
Hierdie situasie dui vir ons die behoefte aanpas die huidige kontrole-indeks by die lengte van die skikking wat saamgevoeg word.
Saamvoegskema vir geordende rye (A en B) van verskillende lengtes:
- As die lengte van beide rye groter as 0 is, vergelyk A[0] en B[0] en skuif die kleiner een na die buffer.
- As die lengte van een van die rye 0 is, neem die oorblywende elemente van die tweede ry en, sonder om hul volgorde te verander, beweeg na die einde van die buffer.
Implementering van die tweede fase
'n Voorbeeld van die koppeling van twee gesorteerde skikkings in Java word hieronder gegee.
int a1=nuwe int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=nuwe int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=nuwe int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } anders if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } anders as (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } anders { int b=a2[j]; a3[k]=b; j++; } }
Hier:
- a1 en a2 is die oorspronklike gesorteerde skikkings wat saamgevoeg moet word;
- a3 – finale skikking;
- i en j is indekse van huidige elemente vir skikkings a1 en a2.
Die eerste en tweede indien toestande verseker dat die indekse nie verder gaan as die grootte van die skikking nie. Die derde en vierde toestandblokke, onderskeidelik, word na die resulterende skikking van die kleiner element geskuif.
Verdeel en heers
So, ons het geleer om die gesorteerde saam te voegversamelings van waardes. Daar kan gesê word dat die tweede deel van die samesmeltingssorteeralgoritme - die samesmelting self - reeds gesorteer is.
Jy moet egter nog verstaan hoe om van die oorspronklike ongesorteerde reeks getalle na verskeie gesorteerde getalle te kom wat saamgevoeg kan word.
Kom ons kyk na die eerste fase van die algoritme en leer hoe om skikkings te skei.
Dit is nie moeilik nie - die oorspronklike lys van waardes word in die helfte gedeel, dan word elke deel ook verdeel, ensovoorts totdat baie klein blokkies verkry word.
Die lengte van sulke minimale elemente kan gelyk wees aan een, dit wil sê, hulle kan self 'n gesorteerde skikking wees, maar dit is nie 'n noodsaaklike voorwaarde nie. Die grootte van die blok word vooraf bepaal, en enige geskikte sorteeralgoritme wat doeltreffend werk met skikkings van klein groottes (byvoorbeeld, quicksort of insertion sorteer) kan gebruik word om dit te bestel.
Dit lyk so.
// oorspronklike skikking {34, 95, 10, 2, 102, 70}; // eerste verdeling {34, 95, 10} en {2, 102, 70}; // tweede verdeling {34} en {95, 10} en {2} en {102, 70}
Die gevolglike blokke, wat uit 1-2 elemente bestaan, is baie maklik om te rangskik.
Daarna moet jy die reeds gesorteerde klein skikkings in pare saamvoeg, en die volgorde van die lede behou, wat ons reeds geleer het om te doen.
Implementering van die eerste fase
Rekursiewe partisionering van 'n skikking word hieronder getoon.
void mergeSorteer(T a, lang begin, lang eindpunt) { long split; as(begin < eindig) { split=(begin + eindpunt)/2; mergeSort (a, begin, verdeel); mergeSort(a, split+1, finish); saamsmelt(a, begin, verdeel, eindig); } }
Wat gebeur in hierdie kode:
-
Die mergeSort-funksie kry die aanvanklike skikking
a
en die linker- en regtergrense van die streek om gesorteer te word (indekse begin en
- finish).
-
As die lengte van hierdie gedeelte groter as een is (
begin < finish
), dan word dit in twee dele verdeel (volgens indeks
- split), en elkeen word rekursief gesorteer.
-
In die rekursiewe funksie-oproep vir die linkerkant, word die beginindeks van die plot en die indeks
split
geslaag. Vir die regte een, onderskeidelik, sal die begin
- (split + 1) wees, en die einde sal die laaste indeks van die oorspronklike afdeling wees.
-
Function
merge
kry twee geordende rye (
a[begin]…a[split]
en
- a[split] +1]…a[voltooi]) en voeg hulle in sorteervolgorde saam.
Die meganika van die samesmeltingsfunksie word hierbo bespreek.
Algemene skema van die algoritme
Die samesmeltingssorteerskikkingsmetode bestaan uit twee groot stappe:
- Verdeel die ongesorteerde oorspronklike skikking in klein stukkies.
- Versamel hulle in pare, volgens die sorteerreël.
'n Groot en komplekse taak word opgedeel in baie eenvoudiges, wat opeenvolgend opgelos word, wat lei tot die gewenste resultaat.
Metode-evaluering
Die tydskompleksiteit van samesmeltingssortering word bepaal deur die hoogte van die gesplete boomalgoritme en is gelyk aan die aantal elemente in die skikking (n) keer sy logaritme (log n). So 'n skatting word logaritmies genoem.
Dit is beide 'n voordeel en 'n nadeel van die metode. Sy looptyd verander nie, selfs in die ergste geval, wanneer die oorspronklike skikking in omgekeerde volgorde gesorteer word. Wanneer volledig gesorteerde data egter verwerk word, verskaf die algoritme nie 'n tydwins nie.
Dit is ook belangrik om te let op die geheuekoste van die samesmeltingssorteermetode. Hulle is gelyk aan die grootte van die oorspronklike versameling. In hierdie bykomend toegewese area word 'n gesorteerde skikking uit die stukke saamgestel.
Implementering van die algoritme
Pascal-samevoegingssorteer word hieronder getoon.
Prosedure MergeSort(naam: string; var f: teks); Var a1, a2, s, i, j, kol, tmp: heelgetal; f1, f2: teks; b: boolean Beginkol:=0; Ken toe (f, naam); herstel(f); Alhoewel dit nie EOF(f) is nie, begin lees(f, a1); inc(kol); einde; naby(f); Assign(f1, '{naam van 1ste hulplêer}'); Assign(f2, '{naam van 2de hulplêer}'); s:=1; Terwyl (s<kol) begin Herstel(f); herskryf(f1); herskryf(f2); Vir i:=1 tot kol div 2 begin Read(f, a1); Skryf(f1, a1, ' '); einde; As (kol div 2) mod s0 begin dan tmp:=kol div 2; Terwyl tmp mod s0 wel begin Lees (f, a1); Skryf(f1, a1, ' '); inc(tmp); einde; einde; Alhoewel dit nie EOF(f) is nie, begin Read(f, a2); Skryf(f2, a2, ' '); einde; naby(f); naby(f1); naby(f2); herskryf(f); herstel(f1); herstel(f2); Lees(f1, a1); Lees(f2, a2); Terwyl (nie EOF(f1)) en (nie EOF(f2)) wel begin i:=0; j:=0; b:=waar; Terwyl (b) en (nie EOF(f1)) en (nie EOF(f2)) wel begin If (a1<a2) begin danSkryf(f, a1, ' '); Lees(f1, a1); inc(i); Einde anders begin Skryf(f, a2, ' '); Lees(f2, a2); ink(j); einde; As (i=s) of (j=s) dan b:=onwaar; einde; Indien nie b nie, begin While (i<s) en (nie EOF(f1)) nie Skryf(f, a1, ' '); Lees(f1, a1); inc(i); einde; Terwyl (j<s) en (nie EOF(f2)) wel begin Skryf(f, a2, ' '); Lees(f2, a2); ink(j); einde; einde; einde; Alhoewel dit nie EOF(f1) is nie, begin tmp:=a1; Lees(f1, a1); Indien nie EOF(f1) dan Skryf(f, tmp, ' ') anders Skryf(f, tmp); einde; Alhoewel dit nie EOF(f2) is nie, begin tmp:=a2; Lees(f2, a2); Indien nie EOF(f2) dan Skryf(f, tmp, ' ') anders Skryf(f, tmp); einde; naby(f); naby(f1); naby(f2); s:=s2; einde; Vee uit (f1); Vee uit (f2); Einde;
Visueel lyk die werking van die algoritme so (bo - ongeordende volgorde, onder - geord).
Eksterne datasortering
Daar is baie dikwels 'n behoefte om sekere data in die eksterne geheue van die rekenaar te sorteer. In sommige gevalle is hulle van indrukwekkende grootte en kan hulle nie in RAM geplaas word om toegang daartoe te vergemaklik nie. Vir sulke gevalle word eksterne sorteermetodes gebruik.
Die behoefte om toegang tot eksterne media te verkry, verminder verwerkingstyddoeltreffendheid.
Die kompleksiteit van die werk is dat die algoritme slegs toegang tot een element van die datastroom op 'n slag het. En in hierdie geval word een van die beste resultate getoon deur die samevoegingssorteermetode, wat die elemente van twee lêers opeenvolgend een na die ander kan vergelyk.
Lees data vaneksterne bron, hul verwerking en skryf na die finale lêer word uitgevoer in geordende blokke (reekse). Volgens die manier van werk met die grootte van geordende reekse, is daar twee tipes sortering: eenvoudige en natuurlike samesmelting.
Eenvoudige samesmelting
Met 'n eenvoudige samevoeging is die reekslengte vas.
In die oorspronklike ongesorteerde lêer bestaan alle reekse dus uit een element. Na die eerste stap neem die grootte toe tot twee. Volgende - 4, 8, 16 ensovoorts.
Dit werk so:
- Die bronlêer (f) is verdeel in twee hulplêers - f1, f2.
- Hulle word weer saamgevoeg in een lêer (f), maar terselfdertyd word alle elemente in pare vergelyk en vorm pare. Die reeksgrootte by hierdie stap word twee.
- Stap 1 word herhaal.
- Stap 2 word herhaal, maar die reeds geordende 2'e word saamgevoeg om gesorteerde 4'e te vorm.
- Die lus gaan voort en verhoog die reeks met elke iterasie totdat die hele lêer gesorteer is.
Hoe weet jy dat die buitenste sortering met 'n eenvoudige samevoeging voltooi is?
- nuwe reekslengte (na samesmelting) nie minder as die totale aantal elemente nie;
- net een episode oor;
- Hulplêer f2 is leeg gelaat.
Die nadele van 'n eenvoudige samesmelting is: aangesien die lopielengte op elke samesmelting vasgestel is, sal gedeeltelik geordende data so lank neem om te verwerk as heeltemal ewekansige data.
Natuurlike samesmelting
Hierdie metode beperk nie die lengte niereeks, maar kies die maksimum moontlike.
Sorteeralgoritme:
- Lees die aanvanklike volgorde van lêer f. Die eerste ontvangde element word na die lêer f1 geskryf.
- As die volgende inskrywing aan die sorteervoorwaarde voldoen, word dit daar geskryf, indien nie, dan na die tweede hulplêer f2.
- Op hierdie manier word alle rekords van die bronlêer versprei, en 'n geordende volgorde word in f1 gevorm, wat die huidige grootte van die reeks bepaal.
- Lêers f1 en f2 is saamgevoeg.
- Die siklus herhaal.
Weens die nie-vaste grootte van die reeks, is dit nodig om die einde van die reeks met 'n spesiale karakter te merk. Daarom, wanneer saamsmelt, neem die aantal vergelykings toe. Daarbenewens kan die grootte van een van die hulplêers naby aan die grootte van die oorspronklike wees.
Natuurlike samesmelting is gemiddeld meer doeltreffend as eenvoudige samesmelting met eksterne sorteer.
Kenmerke van die algoritme
Wanneer twee identiese waardes vergelyk word, behou die metode hul oorspronklike volgorde, dit wil sê, dit is stabiel.
Die sorteerproses kan baie suksesvol in verskeie drade verdeel word.
Die video demonstreer duidelik die werking van die samesmeltingssorteeralgoritme.
