Ang Merge sort ay isa sa mga pangunahing computer science algorithm, na binuo noong 1945 ng mahusay na mathematician na si John von Neumann. Habang nakikilahok sa Manhattan Project, si Neumann ay nahaharap sa pangangailangan na mahusay na magproseso ng malaking halaga ng data. Ang pamamaraan na kanyang binuo ay gumamit ng prinsipyo ng "divide and conquer", na makabuluhang nagbawas ng oras na kinakailangan para sa trabaho.
Prinsipyo at paggamit ng algorithm
Ginagamit ang paraan ng merge sort sa mga problema sa pag-uuri ng mga istruktura na nag-utos ng access sa mga elemento, gaya ng mga array, listahan, stream.
Sa panahon ng pagpoproseso, ang paunang data block ay nahahati sa maliliit na bahagi, hanggang sa isang elemento, na sa katunayan ay isa nang pinagsunod-sunod na listahan. Pagkatapos ito ay muling binuo sa tamang pagkakasunud-sunod.
Ang pag-uuri ng array na may partikular na haba ay nangangailangan ng karagdagang memory area na may parehong laki, kung saan ang pinagsunod-sunod na array ay kinokolekta sa mga bahagi.
Maaaring gamitin ang paraan para mag-order ng anumang maihahambing na uri ng data, gaya ng mga numero o string.
Pagsamahin ang pinagsunod-sunodmga plot
Upang maunawaan ang algorithm, simulan natin ang pagsusuri nito mula sa dulo - mula sa mekanismo ng pagsasama-sama ng mga pinagsunod-sunod na bloke.
Isipin natin na mayroon tayong dalawang array ng mga numero na pinagbukud-bukod sa anumang paraan na kailangang pagsamahin sa isa't isa upang hindi masira ang pag-uuri. Para sa pagiging simple, pag-uuri-uriin namin ang mga numero sa pataas na pagkakasunud-sunod.
Elementary na halimbawa: ang parehong array ay binubuo ng isang elemento bawat isa.
int arr1={31}; int arr2={18};
Upang pagsamahin ang mga ito, kailangan mong kunin ang zero na elemento ng unang array (huwag kalimutan na ang pagnunumero ay nagsisimula sa zero) at ang zero na elemento ng pangalawang array. Ang mga ito ay, ayon sa pagkakabanggit, 31 at 18. Ayon sa kondisyon ng pag-uuri, ang numero 18 ay dapat mauna, dahil ito ay mas mababa. Ilagay lang ang mga numero sa tamang pagkakasunod-sunod:
int resulta={18, 31};
Tingnan natin ang isang mas kumplikadong halimbawa, kung saan ang bawat array ay binubuo ng ilang elemento:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Ang merge algorithm ay binubuo ng sunud-sunod na paghahambing ng mas maliliit na elemento at paglalagay ng mga ito sa resultang array sa tamang pagkakasunod-sunod. Upang masubaybayan ang kasalukuyang mga indeks, ipakilala natin ang dalawang variable - index1 at index2. Sa una, itinakda namin ang mga ito sa zero, dahil ang mga array ay pinagsunod-sunod, at ang pinakamaliit na elemento ay nasa simula.
int index1=0; int index2=0;
Isulat natin ang buong proseso ng pagsasama nang sunud-sunod:
- Kunin ang elementong may index1 mula sa array arr1, at ang elementong may index2 mula sa array arr2.
- Ihambing, piliin ang pinakamaliit sa kanila at ilagaynagreresultang array.
- Dagdagan ng 1 ang kasalukuyang index ng mas maliit na elemento.
- Magpatuloy mula sa unang hakbang.
Sa unang orbit, magiging ganito ang sitwasyon:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; resulta[0]=arr1[0]; // resulta=[2]
Sa pangalawang pagliko:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; resulta[1]=arr2[0]; // resulta=[2, 5]
Pangatlo:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; resulta[2]=arr2[1]; // resulta=[2, 5, 6]
At iba pa, hanggang sa maging ganap na pinagsunod-sunod na array ang resulta: {2, 5, 6, 17, 21, 19, 30, 45}.
Maaaring magkaroon ng ilang partikular na problema kung pagsasamahin ang mga array na may iba't ibang haba. Paano kung naabot na ng isa sa mga kasalukuyang index ang huling elemento, at may natitira pang mga miyembro sa pangalawang array?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 hakbang index1=0, index2=0; 1 2 resulta={1, 2}; // 3 hakbang index1=1, index2=1; 4 < 5 resulta={1, 2, 4}; //4 step index1=2, index2=1 ??
Naabot ng index1 variable ang value 2, ngunit ang arr1 array ay walang elementong may index na iyon. Ang lahat ay simple dito: ilipat lang ang natitirang mga elemento ng pangalawang array sa resultang isa, pinapanatili ang kanilang pagkakasunud-sunod.
result={1, 2, 4, 5, 6, 7, 9};
Ang sitwasyong ito ay nagpapahiwatig sa atin ng pangangailangantumugma sa kasalukuyang check index sa haba ng array na pinagsasama.
Pagsamahin ang scheme para sa mga ordered sequence (A at B) na magkaiba ang haba:
- Kung ang haba ng parehong sequence ay mas malaki sa 0, ihambing ang A[0] at B[0] at ilipat ang mas maliit sa buffer.
- Kung ang haba ng isa sa mga sequence ay 0, kunin ang natitirang mga elemento ng pangalawang sequence at, nang hindi binabago ang kanilang pagkakasunud-sunod, lumipat sa dulo ng buffer.
Pagpapatupad ng ikalawang yugto
Ang isang halimbawa ng pagsali sa dalawang pinagsunod-sunod na array sa Java ay ibinigay sa ibaba.
int a1=bagong int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=bagong int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=bagong int[a1.length + a2.length]; int i=0, j=0; para sa (int k=0; k a1.length-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++; } else { int b=a2[j]; a3[k]=b; j++; } }
Narito:
- Ang a1 at a2 ay ang orihinal na pinagsunod-sunod na mga array na isasama;
- a3 – huling hanay;
- Ang i at j ay mga index ng kasalukuyang elemento para sa mga array a1 at a2.
Ang una at pangalawa kung tinitiyak ng mga kundisyon na ang mga index ay hindi lalampas sa laki ng array. Ang ikatlo at ikaapat na mga bloke ng kundisyon, ayon sa pagkakabanggit, ay inililipat sa nagreresultang hanay ng mas maliit na elemento.
Hatiin at Lupigin
Kaya, natutunan naming pagsamahin ang pinagsunod-sunodmga koleksyon ng mga halaga. Masasabing ang pangalawang bahagi ng merge sort algorithm - ang merge mismo - ay naayos na.
Gayunpaman, kailangan mo pa ring maunawaan kung paano makuha mula sa orihinal na hindi pinagsunod-sunod na hanay ng mga numero patungo sa ilang pinagsunod-sunod na mga numero na maaaring pagsamahin.
Isaalang-alang natin ang unang yugto ng algorithm at alamin kung paano paghiwalayin ang mga array.
Hindi ito mahirap - ang orihinal na listahan ng mga halaga ay nahahati sa kalahati, pagkatapos ay pinaghiwa-hiwalay din ang bawat bahagi, at iba pa hanggang sa makuha ang napakaliit na mga bloke.
Ang haba ng gayong kaunting elemento ay maaaring katumbas ng isa, ibig sabihin, maaari silang maging isang pinagsunod-sunod na hanay, ngunit hindi ito isang kinakailangang kundisyon. Ang laki ng block ay natutukoy nang maaga, at anumang angkop na algorithm ng pag-uuri na mahusay na gumagana sa mga array ng maliliit na laki (halimbawa, quicksort o insertion sort) ay maaaring gamitin para i-order ito.
Mukhang ganito.
// orihinal na array {34, 95, 10, 2, 102, 70}; // unang hati {34, 95, 10} at {2, 102, 70}; // pangalawang hati {34} at {95, 10} at {2} at {102, 70}
Ang mga resultang bloke, na binubuo ng 1-2 elemento, ay napakadaling ayusin.
Pagkatapos nito, kailangan mong pagsamahin ang mga nakaayos nang maliliit na array nang pares, na pinapanatili ang pagkakasunud-sunod ng mga miyembro, na natutunan na naming gawin.
Pagpapatupad ng unang yugto
Recursive partitioning ng isang array ay ipinapakita sa ibaba.
void mergeSort(T a, mahabang simula, mahabang pagtatapos) { mahabang hati; kung(simula < tapusin) { split=(simula + tapusin)/2; mergeSort(a, simulan, split); mergeSort(a, split+1, finish); pagsamahin(a, simulan, hatiin, tapusin); } }
Ano ang mangyayari sa code na ito:
-
Nakukuha ng mergeSort function ang paunang array
a
at ang kaliwa at kanang mga hangganan ng rehiyon na pag-uuri-uriin (nagsisimula ang mga indeks at
- tapos).
-
Kung ang haba ng seksyong ito ay higit sa isa (
simula < tapusin
), pagkatapos ay hahatiin ito sa dalawang bahagi (sa pamamagitan ng index
- split), at ang bawat isa ay recursively sorted.
-
Sa recursive function na tawag para sa kaliwang bahagi, ang panimulang index ng plot at ang index na
split
ay ipinapasa. Para sa tama, ayon sa pagkakabanggit, ang simula ay magiging
- (split + 1), at ang dulo ay ang huling index ng orihinal na seksyon.
Ang
-
Function
merge
ay nakakakuha ng dalawang ordered sequence (
a[start]…a[split]
at
- a[split +1]…a[finish]) at pinagsama ang mga ito sa pagkakasunud-sunod.
Ang mga mekanika ng merge function ay tinalakay sa itaas.
Pangkalahatang scheme ng algorithm
Ang paraan ng merge sort array ay binubuo ng dalawang malalaking hakbang:
- Hatiin ang hindi naayos na orihinal na hanay sa maliliit na piraso.
- Kolektahin ang mga ito nang pares, ayon sa panuntunan sa pag-uuri.
Ang isang malaki at masalimuot na gawain ay hinati-hati sa maraming simple, na sunud-sunod na nalutas, na humahantong sa nais na resulta.
Pagsusuri ng pamamaraan
Ang pagiging kumplikado ng oras ng pagsasama-sama ay tinutukoy ng taas ng split treealgorithm at katumbas ng bilang ng mga elemento sa array (n) na beses sa logarithm nito (log n). Ang nasabing pagtatantya ay tinatawag na logarithmic.
Ito ay parehong kalamangan at disadvantage ng pamamaraan. Ang oras ng pagpapatakbo nito ay hindi nagbabago kahit na sa pinakamasamang kaso, kapag ang orihinal na hanay ay pinagsunod-sunod sa reverse order. Gayunpaman, kapag pinoproseso ang ganap na pinagsunod-sunod na data, ang algorithm ay hindi nagbibigay ng pagtaas ng oras.
Mahalaga ring tandaan ang halaga ng memorya ng paraan ng pagsasama-sama. Ang mga ito ay katumbas ng laki ng orihinal na koleksyon. Sa karagdagang inilaan na lugar na ito, isang pinagsunod-sunod na hanay ay binuo mula sa mga piraso.
Pagpapatupad ng algorithm
Pascal merge sort ay ipinapakita sa ibaba.
Procedure MergeSort(pangalan: string; var f: text); Var a1, a2, s, i, j, kol, tmp: integer; f1, f2: teksto; b: boolean Begincol:=0; Italaga(f, pangalan); i-reset(f); Habang hindi EOF(f) ang nagsisimulang magbasa(f, a1); inc(col); wakas; malapit (f); Italaga(f1, '{pangalan ng 1st auxiliary file}'); Italaga(f2, '{pangalan ng 2nd auxiliary file}'); s:=1; Habang ang (s<kol) ay nagsisimula sa I-reset (f); muling isulat(f1); muling isulat(f2); Para sa i:=1 hanggang kol div 2 simulan ang Read(f, a1); Isulat(f1, a1, ' '); wakas; Kung (kol div 2) mod s0 pagkatapos ay simulan ang tmp:=kol div 2; Habang ang tmp mod s0 ay nagsisimulang Magbasa(f, a1); Isulat(f1, a1, ' '); inc(tmp); wakas; wakas; Bagama't hindi EOF(f) ang nagsisimulang Magbasa(f, a2); Isulat(f2, a2, ' '); wakas; malapit (f); malapit (f1); malapit (f2); muling isulat(f); i-reset(f1); i-reset(f2); Basahin(f1, a1); Basahin(f2, a2); Habang ang (hindi EOF(f1)) at (hindi EOF(f2)) ay nagsisimula sa i:=0; j:=0; b:=totoo; Habang ang (b) at (hindi EOF(f1)) at (hindi EOF(f2)) ay nagsisimula Kung (a1<a2) pagkatapos ay magsisimulaIsulat(f, a1, ' '); Basahin(f1, a1); inc(i); End else begin Write(f, a2, ' '); Basahin(f2, a2); inc(j); wakas; Kung (i=s) o (j=s) kung gayon b:=false; wakas; Kung hindi b pagkatapos ay simulan ang Habang (i<s) at (hindi EOF(f1)) simulan ang Write(f, a1, ' '); Basahin(f1, a1); inc(i); wakas; Habang ang (j<s) at (hindi EOF(f2)) ay nagsisimula sa Write(f, a2, ' '); Basahin(f2, a2); inc(j); wakas; wakas; wakas; Habang hindi EOF(f1) ang nagsisimula tmp:=a1; Basahin(f1, a1); Kung hindi EOF(f1) then Write(f, tmp, ' ') else Write(f, tmp); wakas; Habang hindi EOF(f2) ang nagsisimula tmp:=a2; Basahin(f2, a2); Kung hindi EOF(f2) then Write(f, tmp, ' ') else Write(f, tmp); wakas; malapit (f); malapit (f1); malapit (f2); s:=s2; wakas; Burahin(f1); Burahin(f2); Wakas;
Visually, ganito ang hitsura ng operasyon ng algorithm (itaas - hindi ayos na pagkakasunud-sunod, ibaba - nakaayos).
Pag-uuri ng external na data
Madalas na kailangang pagbukud-bukurin ang ilang data na nasa external memory ng computer. Sa ilang mga kaso, ang mga ito ay may kahanga-hangang laki at hindi maaaring ilagay sa RAM upang mapadali ang pag-access sa kanila. Para sa mga ganitong kaso, ginagamit ang mga panlabas na paraan ng pag-uuri.
Ang pangangailangang mag-access ng external na media ay nagpapababa ng kahusayan sa oras ng pagproseso.
Ang pagiging kumplikado ng trabaho ay ang algorithm ay maaari lamang mag-access ng isang elemento ng stream ng data sa isang pagkakataon. At sa kasong ito, ang isa sa mga pinakamahusay na resulta ay ipinapakita sa pamamagitan ng paraan ng pagsasama-sama, na maaaring ihambing ang mga elemento ng dalawang file nang sunud-sunod.
Pagbabasa ng data mula sapanlabas na mapagkukunan, ang kanilang pagproseso at pagsulat sa panghuling file ay isinasagawa sa mga order na bloke (serye). Ayon sa paraan ng pagtatrabaho sa laki ng nakaayos na serye, may dalawang uri ng pag-uuri: simple at natural na pagsasama.
Simple merge
Sa simpleng pagsasama, naayos ang haba ng serye.
Kaya, sa orihinal na unsorted na file, ang lahat ng serye ay binubuo ng isang elemento. Pagkatapos ng unang hakbang, ang laki ay tataas sa dalawa. Susunod - 4, 8, 16 at iba pa.
Gumagawa ito ng ganito:
- Ang source file (f) ay nahahati sa dalawang auxiliary - f1, f2.
- Muling pinagsama ang mga ito sa isang file (f), ngunit sa parehong oras ang lahat ng mga elemento ay inihahambing sa mga pares at mga pares ng form. Ang laki ng serye sa hakbang na ito ay nagiging dalawa.
- Nauulit ang Hakbang 1.
- Step 2 ay inuulit, ngunit ang na-order na 2s ay pinagsama-sama upang bumuo ng pinagsunod-sunod na 4s.
- Nagpapatuloy ang loop, pinapataas ang serye sa bawat pag-ulit, hanggang sa pagbukud-bukurin ang buong file.
Paano mo malalaman na kumpleto na ang panlabas na pag-uuri na may simpleng pagsasanib?
- bagong haba ng serye (pagkatapos pagsamahin) na hindi bababa sa kabuuang bilang ng mga elemento;
- isang episode na lang ang natitira;
- Axiliary file f2 ay iniwang walang laman.
Ang mga disadvantage ng isang simpleng pagsasama ay: dahil ang haba ng pagtakbo ay nakatakda sa bawat merge pass, ang bahagyang naayos na data ay tatagal upang maproseso bilang ganap na random na data.
Natural na pagsasanib
Hindi nililimitahan ng paraang ito ang habaserye, ngunit pinipili ang maximum na posible.
Algoritmo ng pag-uuri:
- Pagbasa ng unang pagkakasunod-sunod mula sa file f. Ang unang natanggap na elemento ay nakasulat sa file na f1.
- Kung ang susunod na entry ay nakakatugon sa kondisyon ng pag-uuri, ito ay nakasulat doon, kung hindi, pagkatapos ay sa pangalawang auxiliary file f2.
- Sa ganitong paraan, ang lahat ng record ng source file ay ipinamamahagi, at nabuo ang isang ordered sequence sa f1, na tumutukoy sa kasalukuyang laki ng series.
- Ang mga file na f1 at f2 ay pinagsama.
- Nauulit ang cycle.
Dahil sa hindi nakapirming laki ng serye, kinakailangang markahan ang dulo ng sequence ng isang espesyal na karakter. Samakatuwid, kapag pinagsama, ang bilang ng mga paghahambing ay tumataas. Bilang karagdagan, ang laki ng isa sa mga auxiliary file ay maaaring malapit sa laki ng orihinal.
Sa karaniwan, ang natural na pagsasanib ay mas mahusay kaysa sa simpleng pagsasanib na may panlabas na pag-uuri.
Mga tampok ng algorithm
Kapag naghahambing ng dalawang magkaparehong halaga, pinapanatili ng pamamaraan ang orihinal na pagkakasunud-sunod nito, ibig sabihin, ito ay matatag.
Ang proseso ng pag-uuri ay maaaring matagumpay na hatiin sa maramihang mga thread.
Malinaw na ipinapakita ng video ang pagpapatakbo ng merge sort algorithm.
