Merge sort ni mojawapo ya kanuni za msingi za sayansi ya kompyuta, iliyoundwa mwaka wa 1945 na mwanahisabati mkuu John von Neumann. Wakati akishiriki katika Mradi wa Manhattan, Neumann alikabiliwa na hitaji la kuchakata kwa ufanisi idadi kubwa ya data. Mbinu aliyobuni ilitumia kanuni ya "gawanya na kushinda", ambayo ilipunguza kwa kiasi kikubwa muda unaohitajika kufanya kazi.
Kanuni na matumizi ya kanuni
Mbinu ya kupanga ya kuunganisha hutumiwa katika matatizo ya kupanga miundo ambayo imeamuru ufikiaji wa vipengele, kama vile mkusanyiko, orodha, mitiririko.
Wakati wa kuchakata, kizuizi cha awali cha data kinagawanywa katika vipengele vidogo, hadi kipengele kimoja, ambacho kwa kweli ni orodha iliyopangwa. Kisha inakusanywa tena kwa mpangilio sahihi.
Kupanga safu ya urefu fulani kunahitaji eneo la ziada la kumbukumbu la ukubwa sawa, ambapo safu iliyopangwa inakusanywa katika sehemu.
Mbinu inaweza kutumika kuagiza aina yoyote ya data inayoweza kulinganishwa, kama vile nambari au mifuatano.
Unganisha umepangwaviwanja
Ili kuelewa kanuni, hebu tuanze uchanganuzi wake kutoka mwisho - kutoka kwa utaratibu wa kuunganisha vitalu vilivyopangwa.
Hebu fikiria kuwa tuna safu mbili za nambari zilizopangwa kwa njia yoyote ambayo inahitaji kuunganishwa ili upangaji usivunjwe. Kwa urahisi, tutapanga nambari kwa mpangilio wa kupanda.
Mfano wa kimsingi: safu zote mbili zina kipengele kimoja kila moja.
int arr1={31}; int arr2={18};
Ili kuziunganisha, unahitaji kuchukua kipengele cha sifuri cha safu ya kwanza (usisahau kwamba nambari huanza kutoka sifuri) na kipengele cha sifuri cha safu ya pili. Hizi ni, kwa mtiririko huo, 31 na 18. Kwa mujibu wa hali ya kupanga, nambari ya 18 inapaswa kuja kwanza, kwa kuwa ni chini. Weka tu nambari kwa mpangilio sahihi:
int tokeo={18, 31};
Hebu tuangalie mfano changamano zaidi, ambapo kila safu ina vipengele kadhaa:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoriti ya kuunganisha itajumuisha kulinganisha vipengele vidogo kwa kufuatana na kuviweka katika safu inayotokana katika mpangilio ufaao. Ili kufuatilia fahirisi za sasa, hebu tuanzishe vigezo viwili - index1 na index2. Hapo awali, tuliziweka hadi sifuri, kwa kuwa safu zimepangwa, na vipengele vidogo zaidi viko mwanzoni.
int index1=0; int index2=0;
Hebu tuandike mchakato mzima wa kuunganisha hatua kwa hatua:
- Chukua kipengee kilicho na index1 kutoka kwa safu arr1, na kipengele kilicho na index2 kutoka kwa safu arr2.
- Linganisha, chagua ndogo zaidi kati yao na uwekesafu inayotokana.
- Ongeza faharasa ya sasa ya kipengele kidogo kwa 1.
- Endelea kutoka hatua ya kwanza.
Kwenye obiti ya kwanza, hali itakuwa kama hii:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; matokeo[0]=arr1[0]; // matokeo=[2]
Katika zamu ya pili:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; matokeo[1]=arr2[0]; // matokeo=[2, 5]
Tatu:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; matokeo[2]=arr2[1]; // matokeo=[2, 5, 6]
Na kadhalika, hadi matokeo yawe safu iliyopangwa kabisa: {2, 5, 6, 17, 21, 19, 30, 45}.
Tatizo fulani zinaweza kutokea ikiwa safu zenye urefu tofauti zitaunganishwa. Je, ikiwa mojawapo ya faharasa za sasa imefikia kipengele cha mwisho, na bado kuna washiriki waliosalia katika safu ya pili?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 hatua index1=0, index2=0; 1 2 matokeo={1, 2}; // 3 hatua index1=1, index2=1; 4 < 5 matokeo={1, 2, 4}; // 4 hatua index1=2, index2=1 ??
Kigezo cha index1 kimefikia thamani ya 2, lakini safu arr1 haina kipengele chenye faharasa hiyo. Kila kitu ni rahisi hapa: kuhamisha tu vipengele vilivyobaki vya safu ya pili kwa moja inayosababisha, kuhifadhi mpangilio wao.
matokeo={1, 2, 4, 5, 6, 7, 9};
Hali hii inatuonyesha hitajilinganisha faharasa ya tiki ya sasa na urefu wa safu inayounganishwa.
Unganisha mpango wa mfuatano uliopangwa (A na B) wa urefu tofauti:
- Ikiwa urefu wa mfuatano wote ni mkubwa kuliko 0, linganisha A[0] na B[0] na usogeze mdogo zaidi hadi kwenye bafa.
- Ikiwa urefu wa mojawapo ya mfuatano ni 0, chukua vipengele vilivyosalia vya mfuatano wa pili na, bila kubadilisha mpangilio wao, nenda hadi mwisho wa bafa.
Utekelezaji wa hatua ya pili
Mfano wa kuunganisha safu mbili zilizopangwa katika Java umetolewa hapa chini.
int a1=int mpya {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=int mpya {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=int mpya[a1.length + a2.length]; int i=0, j=0; kwa (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } mwingine ikiwa (j > a2.length-1) { int a=a1; a3[k]=a; i++; } mwingine ikiwa (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } mwingine { int b=a2[j]; a3[k]=b; j++; } }
Hapa:
- a1 na a2 ni safu asili zilizopangwa ili kuunganishwa;
- a3 – safu ya mwisho;
- i na j ni faharasa za vipengele vya sasa vya safu a1 na a2.
Ya kwanza na ya pili ikiwa hali zitahakikisha kwamba faharasa hazizidi saizi ya safu. Vizuizi vya hali ya tatu na nne, mtawalia, vinahamishwa hadi safu inayotokana ya kipengele kidogo.
Gawa na Ushinde
Kwa hivyo, tumejifunza kuunganisha vilivyopangwamakusanyo ya maadili. Inaweza kusemwa kuwa sehemu ya pili ya algoriti ya kupanga - kuunganisha yenyewe - tayari imepangwa.
Hata hivyo, bado unahitaji kuelewa jinsi ya kupata kutoka safu asili ya nambari ambazo hazijapangwa hadi kadhaa zilizopangwa ambazo zinaweza kuunganishwa.
Hebu tuzingatie hatua ya kwanza ya kanuni na tujifunze jinsi ya kutenganisha safu.
Hii sio ngumu - orodha asili ya maadili imegawanywa kwa nusu, kisha kila sehemu imegawanywa mara mbili, na kadhalika hadi vizuizi vidogo sana vipatikane.
Urefu wa vipengee vidogo kama hivyo vinaweza kuwa sawa na moja, yaani, vinaweza kuwa safu iliyopangwa, lakini hili si sharti la lazima. Ukubwa wa kizuizi huamuliwa mapema, na algoriti yoyote inayofaa ya kupanga ambayo inafanya kazi kwa ufanisi na safu za saizi ndogo (kwa mfano, upangaji wa haraka au uwekaji) inaweza kutumika kuiagiza.
Inaonekana hivi.
// safu asili {34, 95, 10, 2, 102, 70}; // mgawanyiko wa kwanza {34, 95, 10} na {2, 102, 70}; // mgawanyiko wa sekunde {34} na {95, 10} na {2} na {102, 70}
Vizuizi vinavyotokana, vinavyojumuisha vipengele 1-2, ni rahisi sana kupanga.
Baada ya hapo, unahitaji kuunganisha safu ndogo zilizopangwa tayari katika jozi, kuhifadhi mpangilio wa washiriki, ambao tayari tumejifunza kufanya.
Utekelezaji wa hatua ya kwanza
Ugawaji unaorudiwa wa safu umeonyeshwa hapa chini.
void mergeSort(T a, mwanzo mrefu, mwisho mrefu) { mgawanyiko mrefu; kama(anza < kumaliza) { mgawanyiko=(anza + kumaliza) / 2; unganishaPanga(a, anza, gawanya); unganishaPanga(a, gawanya+1, maliza); unganisha(a, anza, gawanya, maliza); } }
Nini hufanyika katika msimbo huu:
-
Kitendakazi cha mergeSort kinapata safu ya awali
a
na mipaka ya kushoto na kulia ya eneo ili kupangwa (fahirisi zinaanza na
- kumaliza).
-
Ikiwa urefu wa sehemu hii ni kubwa kuliko moja (
anza < maliza
), basi itagawanywa katika sehemu mbili (kwa faharasa
- mgawanyiko), na kila moja imepangwa kwa kujirudia.
-
Katika simu ya utendakazi inayojirudia kwa upande wa kushoto, faharasa ya kuanzia ya njama na faharasa
mgawanyiko
hupitishwa. Kwa ile inayofaa, mtawalia, mwanzo utakuwa
- (mgawanyiko + 1), na mwisho utakuwa faharasa ya mwisho ya sehemu asili.
-
Function
merge
inapata mifuatano miwili iliyoagizwa (
a[anza]…a[split]
na
- a[mgawanyiko +1]…a[malizia]) na kuziunganisha kwa mpangilio wa kupanga.
Mitindo ya chaguo la kukokotoa la kuunganisha imejadiliwa hapo juu.
Mpango wa jumla wa kanuni
Njia ya kuunganisha ya safu ya kupanga ina hatua mbili kubwa:
- Gawanya safu asili ambayo haijapangwa katika vipande vidogo.
- Zikusanye kwa jozi, kwa kufuata kanuni ya kupanga.
Kazi kubwa na changamano imegawanywa katika nyingi rahisi, ambazo hutatuliwa kwa kufuatana, na hivyo kusababisha matokeo yanayotarajiwa.
Tathmini ya mbinu
Utata wa muda wa aina ya kuunganisha hubainishwa na urefu wa mti uliopasuliwaalgorithm na ni sawa na idadi ya vipengele katika safu (n) mara logarithm yake (logi n). Kadirio kama hilo linaitwa logarithmic.
Hii ni faida na hasara ya mbinu. Wakati wake wa kukimbia haubadilika hata katika hali mbaya zaidi, wakati safu ya awali imepangwa kwa utaratibu wa nyuma. Hata hivyo, wakati wa kuchakata data iliyopangwa kabisa, kanuni haitoi faida ya wakati.
Ni muhimu pia kuzingatia gharama ya kumbukumbu ya mbinu ya kuunganisha. Zinalingana na saizi ya mkusanyiko asilia. Katika eneo hili lililotengwa zaidi, safu iliyopangwa inakusanywa kutoka kwa vipande.
Utekelezaji wa kanuni
Pascal merge sort inaonekana hapa chini.
Taratibu UnganishaPanga(jina: mfuatano; var f: maandishi); Var a1, a2, s, i, j, kol, tmp: integer; f1, f2: maandishi; b: boolean Begincol:=0; Agiza(f, jina); weka upya(f); Ingawa si EOF(f) kuanza kusoma(f, a1); inc(col); mwisho; funga(f); Agiza(f1, '{jina la faili 1-kisaidizi}'); Agiza(f2, '{jina la faili 2-saidizi}'); s:=1; Wakati (s<kol) inaanza Kuweka Upya(f); andika upya(f1); andika upya(f2); Kwa i:=1 hadi kol div 2 huanza Kusoma(f, a1); Andika(f1, a1, ' '); mwisho; Ikiwa (kol div 2) mod s0 basi anza tmp:=kol div 2; Wakati tmp mod s0 huanza Kusoma (f, a1); Andika(f1, a1, ' '); inc(tmp); mwisho; mwisho; Ingawa si EOF(f) kuanza Kusoma(f, a2); Andika(f2, a2, ' '); mwisho; funga(f); funga(f1); funga(f2); andika upya(f); weka upya(f1); weka upya(f2); Soma(f1, a1); Soma(f2, a2); Wakati (sio EOF(f1)) na (sio EOF(f2)) huanza i:=0; j:=0; b:=kweli; Wakati (b) na (sio EOF(f1)) na (sio EOF(f2)) huanza Ikiwa (a1<a2) basi anzaAndika(f, a1, ' '); Soma(f1, a1); pamoja (i); Mwisho mwingine anza Andika(f, a2, ' '); Soma(f2, a2); inc(j); mwisho; Ikiwa (i=s) au (j=s) basi b:=sivyo; mwisho; Ikiwa sio b basi anza Wakati (i<s) na (sio EOF(f1)) uanze Andika(f, a1, ' '); Soma(f1, a1); pamoja (i); mwisho; Wakati (j<s) na (si EOF(f2)) zinaanza Andika(f, a2, ' '); Soma(f2, a2); inc(j); mwisho; mwisho; mwisho; Wakati sio EOF(f1) kuanza tmp:=a1; Soma(f1, a1); Ikiwa si EOF(f1) basi Andika(f, tmp, ' ') vinginevyo Andika(f, tmp); mwisho; Wakati sio EOF(f2) kuanza tmp:=a2; Soma(f2, a2); Ikiwa si EOF(f2) basi Andika(f, tmp, ' ') vinginevyo Andika(f, tmp); mwisho; funga(f); funga(f1); funga(f2); s:=s2; mwisho; Futa(f1); Futa(f2); Mwisho;
Kwa mwonekano, utendakazi wa algoriti inaonekana kama hii (juu - mlolongo usiopangwa, chini - uliopangwa).
Upangaji data wa nje
Mara nyingi sana kuna haja ya kupanga baadhi ya data iliyo kwenye kumbukumbu ya nje ya kompyuta. Katika baadhi ya matukio, ni ya ukubwa wa kuvutia na haiwezi kuwekwa kwenye RAM ili kuwezesha upatikanaji wao. Kwa hali kama hizi, mbinu za upangaji wa nje hutumiwa.
Haja ya kufikia midia ya nje hudhoofisha ufanisi wa wakati wa kuchakata.
Utata wa kazi ni kwamba algoriti inaweza tu kufikia kipengele kimoja cha mtiririko wa data kwa wakati mmoja. Na katika kesi hii, mojawapo ya matokeo bora zaidi yanaonyeshwa kwa mbinu ya kuunganisha ya kupanga, ambayo inaweza kulinganisha vipengele vya faili mbili kwa kufuatana moja baada ya nyingine.
Kusoma data kutokachanzo cha nje, usindikaji na uandishi wao kwa faili ya mwisho hufanywa kwa vitalu vilivyoagizwa (mfululizo). Kulingana na njia ya kufanya kazi na saizi ya safu zilizoagizwa, kuna aina mbili za kupanga: kuunganisha rahisi na asili.
Muunganisho rahisi
Kwa muunganisho rahisi, urefu wa mfululizo umewekwa.
Kwa hivyo, katika faili asili ambayo haijapangwa, misururu yote ina kipengele kimoja. Baada ya hatua ya kwanza, ukubwa huongezeka hadi mbili. Inayofuata - 4, 8, 16 na kadhalika.
Inafanya kazi kama hii:
- Faili chanzo (f) imegawanywa katika zile mbili saidizi - f1, f2.
- Zimeunganishwa tena kuwa faili moja (f), lakini wakati huo huo vipengele vyote vinalinganishwa katika jozi na kuunda jozi. Saizi ya mfululizo katika hatua hii inakuwa mbili.
- Hatua ya 1 inarudiwa.
- Hatua ya 2 inarudiwa, lakini 2 zilizoagizwa tayari zimeunganishwa na kuunda 4 zilizopangwa.
- Kitanzi kinaendelea, na kuongeza mfululizo kwa kila marudio, hadi faili nzima itakapopangwa.
Unajuaje kwamba upangaji wa nje kwa muunganisho rahisi umekamilika?
- urefu wa mfululizo mpya (baada ya kuunganishwa) sio chini ya jumla ya idadi ya vipengele;
- kipindi kimoja tu kimesalia;
- Faili saidizi f2 iliachwa tupu.
Hasara za muunganisho rahisi ni: kwa kuwa urefu wa uendeshaji umebainishwa kwa kila pasi ya kuunganisha, data iliyoagizwa kwa sehemu itachukua muda mrefu kuchakatwa kama data nasibu kabisa.
Muunganisho wa asili
Njia hii haipunguzi urefumfululizo, lakini huchagua upeo unaowezekana.
Algorithm ya kupanga:
- Kusoma mlolongo wa kwanza kutoka kwa faili f. Kipengele cha kwanza kilichopokelewa kimeandikwa kwa faili f1.
- Ikiwa ingizo linalofuata linakidhi hali ya kupanga, imeandikwa hapo, ikiwa sivyo, kisha kwa faili msaidizi ya pili f2.
- Kwa njia hii, rekodi zote za faili chanzo husambazwa, na mfuatano uliopangwa unaundwa katika f1, ambayo huamua ukubwa wa sasa wa mfululizo.
- Faili f1 na f2 zimeunganishwa.
- Mzunguko unajirudia.
Kwa sababu ya saizi isiyobadilika ya safu, ni muhimu kuashiria mwisho wa mlolongo kwa herufi maalum. Kwa hiyo, wakati wa kuunganisha, idadi ya kulinganisha huongezeka. Kwa kuongeza, saizi ya mojawapo ya faili saidizi inaweza kuwa karibu na saizi ya asili.
Kwa wastani, muunganisho wa asili una ufanisi zaidi kuliko kuunganisha rahisi na upangaji wa nje.
Vipengele vya kanuni
Unapolinganisha thamani mbili zinazofanana, mbinu huhifadhi mpangilio wao wa asili, yaani, ni thabiti.
Mchakato wa kupanga unaweza kugawanywa kwa mafanikio katika nyuzi nyingi.
Video inaonyesha kwa uwazi utendakazi wa algoriti ya kupanga ya kuunganisha.
