Merge sort është një nga algoritmet bazë të shkencës kompjuterike, i formuluar në vitin 1945 nga matematikani i madh John von Neumann. Ndërsa merrte pjesë në Projektin Manhattan, Neumann u përball me nevojën për të përpunuar në mënyrë efikase sasi të mëdha të dhënash. Metoda që ai zhvilloi përdorte parimin e "përça dhe sundo", i cili reduktoi ndjeshëm kohën e nevojshme për punë.
Parimi dhe përdorimi i algoritmit
Metoda e renditjes së bashkimit përdoret në problemet e renditjes së strukturave që kanë rregulluar aksesin në elementë, të tillë si vargje, lista, transmetime.
Gjatë përpunimit, blloku fillestar i të dhënave ndahet në komponentë të vegjël, deri në një element, që në fakt është tashmë një listë e renditur. Pastaj rimontohet në rendin e duhur.
Rregullimi i një grupi me një gjatësi të caktuar kërkon një zonë shtesë memorie të së njëjtës madhësi, në të cilën grupi i renditur mblidhet në pjesë.
Metoda mund të përdoret për të porositur çdo lloj të dhënash të krahasueshme, si numra ose vargje.
Shkrirja e renditurparcela
Për të kuptuar algoritmin, le ta fillojmë analizën e tij nga fundi - nga mekanizmi i bashkimit të blloqeve të renditura.
Le të imagjinojmë se kemi dy grupe numrash të renditur në çfarëdo mënyre që duhet të kombinohen me njëri-tjetrin në mënyrë që renditja të mos prishet. Për thjeshtësi, ne do t'i renditim numrat në rend rritës.
Shembull elementar: të dy vargjet përbëhen nga një element secili.
int arr1={31}; int arr2={18};
Për t'i bashkuar ato, duhet të merrni elementin zero të grupit të parë (mos harroni se numërimi fillon nga zero) dhe elementin zero të grupit të dytë. Këto janë, përkatësisht, 31 dhe 18. Sipas kushtit të renditjes, numri 18 duhet të jetë i pari, pasi është më i vogël. Thjesht vendosni numrat në rendin e duhur:
int rezultat={18, 31};
Le të shohim një shembull më të komplikuar, ku çdo grup përbëhet nga disa elementë:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Algoritmi i bashkimit do të përbëhet nga krahasimi i njëpasnjëshëm i elementeve më të vegjël dhe vendosja e tyre në grupin që rezulton në rendin e duhur. Për të mbajtur gjurmët e indekseve aktuale, le të prezantojmë dy variabla - index1 dhe index2. Fillimisht i vendosëm në zero, pasi vargjet janë të renditura dhe elementët më të vegjël janë në fillim.
int index1=0; int index2=0;
Le të shkruajmë të gjithë procesin e bashkimit hap pas hapi:
- Merrni elementin me index1 nga grupi arr1 dhe elementin me index2 nga grupi arr2.
- Krahaso, zgjidh më të voglin prej tyre dhe vendosgrup rezultues.
- Rritni indeksin aktual të elementit më të vogël me 1.
- Vazhdo nga hapi i parë.
Në orbitën e parë, situata do të duket kështu:
index1=0; indeksi 2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indeksi 1++; rezultat[0]=arr1[0]; // rezultat=[2]
Në kthesën e dytë:
index1=1; indeksi 2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indeksi2++; rezultat[1]=arr2[0]; // rezultat=[2, 5]
I treti:
index1=1; indeksi 2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indeksi2++; rezultat[2]=arr2[1]; // rezultat=[2, 5, 6]
E kështu me radhë, derisa rezultati të jetë një grup plotësisht i renditur: {2, 5, 6, 17, 21, 19, 30, 45}.
Vështirësi të caktuara mund të shfaqen nëse bashkohen vargje me gjatësi të ndryshme. Po sikur një nga indekset aktuale të ketë arritur elementin e fundit dhe të mbeten ende anëtarë në grupin e dytë?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 hap indeksi1=0, indeksi2=0; 1 2 rezultat={1, 2}; // Indeksi 3 hapash1=1, indeksi2=1; 4 < 5 rezultat={1, 2, 4}; //4 hapi indeksi1=2, indeksi 2=1 ??
Ndryshorja index1 ka arritur vlerën 2, por grupi arr1 nuk ka një element me atë indeks. Gjithçka është e thjeshtë këtu: thjesht transferoni elementët e mbetur të grupit të dytë në atë që rezulton, duke ruajtur renditjen e tyre.
rezultat={1, 2, 4, 5, 6, 7, 9};
Kjo situatë na tregon nevojënpërputhet me indeksin aktual të kontrollit me gjatësinë e grupit që po bashkohet.
Skema e bashkimit për sekuencat e renditura (A dhe B) me gjatësi të ndryshme:
- Nëse gjatësia e të dy sekuencave është më e madhe se 0, krahasoni A[0] dhe B[0] dhe zhvendoseni atë më të vogël në bufer.
- Nëse gjatësia e njërës prej sekuencave është 0, merrni elementët e mbetur të sekuencës së dytë dhe, pa ndryshuar renditjen e tyre, kaloni në fund të tamponit.
Zbatimi i fazës së dytë
Një shembull i bashkimit të dy vargjeve të renditura në Java është dhënë më poshtë.
int a1=int i ri {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=int i ri {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=i ri int[a1.gjatësi + a2.gjatësi]; int i=0, j=0; për (int k=0; k a1.gjatësia-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.gjatesi-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++; } }
Këtu:
- a1 dhe a2 janë grupet origjinale të renditura që do të bashkohen;
- a3 – grupi përfundimtar;
- i dhe j janë indekse të elementeve aktuale për vargjet a1 dhe a2.
E para dhe e dyta nëse kushtet sigurojnë që indekset të mos shkojnë përtej madhësisë së grupit. Blloqet e gjendjes së tretë dhe të katërt, përkatësisht, zhvendosen në grupin rezultues të elementit më të vogël.
Nda dhe sundo
Pra, ne kemi mësuar të bashkojmë të renditurakoleksionet e vlerave. Mund të thuhet se pjesa e dytë e algoritmit të renditjes së bashkimit - vetë bashkimi - tashmë është renditur.
Megjithatë, ju ende duhet të kuptoni se si të kaloni nga grupi origjinal i pazgjedhur i numrave në disa të renditura që mund të bashkohen.
Le të shqyrtojmë fazën e parë të algoritmit dhe të mësojmë se si të ndajmë vargje.
Kjo nuk është e vështirë - lista origjinale e vlerave ndahet në gjysmë, pastaj secila pjesë është gjithashtu e dyfishtë dhe kështu me radhë derisa të merren blloqe shumë të vogla.
Gjatësia e elementeve të tillë minimale mund të jetë e barabartë me një, domethënë, ata vetë mund të jenë një grup i renditur, por ky nuk është një kusht i domosdoshëm. Madhësia e bllokut përcaktohet paraprakisht dhe çdo algoritëm i përshtatshëm klasifikimi që funksionon në mënyrë efikase me grupe të madhësive të vogla (për shembull, renditja e shpejtë ose renditja e futur) mund të përdoret për ta porositur atë.
Duket kështu.
// grupi origjinal {34, 95, 10, 2, 102, 70}; // ndarja e parë {34, 95, 10} dhe {2, 102, 70}; // ndarje e dytë {34} dhe {95, 10} dhe {2} dhe {102, 70}
Blloqet që rezultojnë, të përbërë nga 1-2 elementë, janë shumë të lehta për t'u rregulluar.
Pas kësaj, ju duhet të bashkoni grupet e vogla tashmë të renditura në çifte, duke ruajtur rendin e anëtarëve, gjë që tashmë kemi mësuar ta bëjmë.
Zbatimi i fazës së parë
Ndarja rekursive e një grupi është paraqitur më poshtë.
void mergeSort(T a, fillim i gjatë, përfundim i gjatë) { ndarje e gjatë; nëse(fillimi < finish) { ndarje=(fillim + mbarim)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); bashkim (a, fillimi, ndarja, mbarimi); } }
Çfarë ndodh në këtë kod:
-
Funksioni mergeSort merr grupin fillestar
a
dhe kufijtë majtas dhe djathtas të rajonit që do të renditet (indekset fillojnë dhe
- mbarimi).
-
Nëse gjatësia e këtij seksioni është më e madhe se një (
fillimi < mbarimi
), atëherë ndahet në dy pjesë (me indeks
- ndarje), dhe secila është e renditur në mënyrë rekursive.
-
Në thirrjen e funksionit rekurziv për anën e majtë, kalohet indeksi fillestar i grafikut dhe indeksi
split
. Për të drejtën, përkatësisht, fillimi do të jetë
- (ndarje + 1) dhe fundi do të jetë indeksi i fundit i seksionit origjinal.
-
Funksioni
bashkim
merr dy sekuenca të renditura (
a[start]…a[split]
dhe
- a[ndarje +1]…a[finish]) dhe i bashkon ato sipas renditjes.
Mekanika e funksionit të bashkimit është diskutuar më sipër.
Skema e përgjithshme e algoritmit
Metoda e grupit të renditjes së bashkimit përbëhet nga dy hapa të mëdhenj:
- Ndani grupin origjinal të pazgjedhur në copa të vogla.
- Mblidhi ato në çifte, duke ndjekur rregullin e renditjes.
Një detyrë e madhe dhe komplekse ndahet në shumë të thjeshta, të cilat zgjidhen në mënyrë sekuenciale, duke çuar në rezultatin e dëshiruar.
Vlerësimi i metodës
Kompleksiteti kohor i renditjes së bashkimit përcaktohet nga lartësia e pemës së ndarëalgoritmi dhe është i barabartë me numrin e elementeve në grup (n) herë logaritmin e tij (log n). Një vlerësim i tillë quhet logaritmik.
Ky është një avantazh dhe një disavantazh i metodës. Koha e funksionimit të saj nuk ndryshon as në rastin më të keq, kur grupi origjinal renditet në rend të kundërt. Megjithatë, kur përpunohen të dhëna plotësisht të renditura, algoritmi nuk siguron një fitim kohor.
Është gjithashtu e rëndësishme të shënohet kostoja e memories së metodës së renditjes së bashkimit. Ato janë të barabarta me madhësinë e koleksionit origjinal. Në këtë zonë të caktuar shtesë, një grup i renditur është mbledhur nga pjesët.
Zbatimi i algoritmit
Rendimi i shkrirjes Pascal tregohet më poshtë.
Procedura MergeSort(emri: varg; var f: tekst); Var a1, a2, s, i, j, kol, tmp: numër i plotë; f1, f2: tekst; b: boolean Fillimi:=0; Cakto (f, emri); rivendos (f); Ndërsa jo EOF(f) filloni të lexoni (f, a1); inc(col); fundi; mbyll (f); Assign(f1, '{emri i skedarit 1st ndihmës}'); Assign(f2, '{emri i skedarit të dytë ndihmës}'); s:=1; Ndërsa (s<kol) do të fillojë Reset(f); rishkruaj (f1); rishkruaj (f2); Për i:=1 në kol div 2 do të fillojë Read(f, a1); Shkruani (f1, a1, ' '); fundi; Nëse (kol div 2) mod s0 atëherë filloni tmp:=kol div 2; Ndërsa tmp mod s0 fillon Read(f, a1); Shkruani (f1, a1, ' '); inc(tmp); fundi; fundi; Ndërsa jo EOF(f) fillon Lexo(f, a2); Shkruani (f2, a2, ' '); fundi; mbyll (f); mbyll (f1); mbyll (f2); rishkruaj (f); rivendos (f1); rivendos (f2); Lexoni (f1, a1); Lexoni (f2, a2); Ndërsa (jo EOF(f1)) dhe (jo EOF(f2)) fillojnë i:=0; j:=0; b:=e vërtetë; Ndërsa (b) dhe (jo EOF(f1)) dhe (jo EOF(f2)) fillojnë nëse (a1<a2) atëherë filloniShkruani(f, a1, ' '); Lexoni (f1, a1); inc(i); Fundi tjetër fillon Shkruaj(f, a2, ' '); Lexoni (f2, a2); inc(j); fundi; Nëse (i=s) ose (j=s) atëherë b:=false; fundi; Nëse jo b, atëherë filloni Ndërsa (i<s) dhe (jo EOF(f1)) filloni Write(f, a1, ' '); Lexoni (f1, a1); inc(i); fundi; Ndërsa (j<s) dhe (jo EOF(f2)) fillojnë Write(f, a2, ' '); Lexoni (f2, a2); inc(j); fundi; fundi; fundi; Ndërsa jo EOF(f1) filloni tmp:=a1; Lexoni (f1, a1); Nëse jo EOF(f1) atëherë Write(f, tmp, ' ') tjetër Write(f, tmp); fundi; Ndërsa jo EOF(f2) filloni tmp:=a2; Lexoni (f2, a2); Nëse jo EOF(f2) atëherë Write(f, tmp, ' ') tjetër Write(f, tmp); fundi; mbyll (f); mbyll (f1); mbyll (f2); s:=s2; fundi; Fshij (f1); Fshij (f2); Fund;
Vizualisht, funksionimi i algoritmit duket kështu (lart - sekuencë e parregulluar, poshtë - e renditur).
Rregullimi i të dhënave të jashtme
Shumë shpesh lind nevoja për të renditur disa të dhëna të vendosura në memorien e jashtme të kompjuterit. Në disa raste, ato janë me përmasa mbresëlënëse dhe nuk mund të vendosen në RAM për të lehtësuar aksesin në to. Për raste të tilla përdoren metoda të renditjes së jashtme.
Nevoja për të hyrë në media të jashtme degradon efikasitetin e kohës së përpunimit.
Kompleksiteti i punës është se algoritmi mund të aksesojë vetëm një element të rrjedhës së të dhënave në të njëjtën kohë. Dhe në këtë rast, një nga rezultatet më të mira tregohet nga metoda e renditjes së bashkimit, e cila mund të krahasojë elementët e dy skedarëve në mënyrë sekuenciale njëri pas tjetrit.
Leximi i të dhënave ngaburimi i jashtëm, përpunimi dhe shkrimi i tyre në skedarin përfundimtar kryhen në blloqe (seri) të renditura. Sipas mënyrës së punës me madhësinë e serive të porositura, ekzistojnë dy lloje të renditjes: bashkimi i thjeshtë dhe natyral.
Shkrirje e thjeshtë
Me një bashkim të thjeshtë, gjatësia e serisë është fikse.
Kështu, në skedarin origjinal të pazgjedhur, të gjitha seritë përbëhen nga një element. Pas hapit të parë, madhësia rritet në dy. Tjetra - 4, 8, 16 e kështu me radhë.
Funksionon kështu:
- Skedari burimor (f) është i ndarë në dy ndihmës - f1, f2.
- Ato përsëri shkrihen në një skedar (f), por në të njëjtën kohë të gjithë elementët krahasohen në çifte dhe formojnë çifte. Madhësia e serisë në këtë hap bëhet dy.
- Hapi 1 përsëritet.
- Hapi 2 përsëritet, por 2-të e renditura tashmë janë bashkuar për të formuar 4-të e renditura.
- Cakulli vazhdon, duke rritur serinë në çdo përsëritje, derisa i gjithë skedari të renditet.
Si e dini se renditja e jashtme me një bashkim të thjeshtë ka përfunduar?
- gjatësia e serisë së re (pas bashkimit) jo më pak se numri total i elementeve;
- ka mbetur vetëm një episod;
- Skedari ndihmës f2 u la bosh.
Disavantazhet e një bashkimi të thjeshtë janë: meqenëse gjatësia e ekzekutimit është e fiksuar në çdo kalim bashkimi, të dhënat e renditura pjesërisht do të marrin aq kohë për t'u përpunuar sa të dhëna krejtësisht të rastësishme.
Fusion natyror
Kjo metodë nuk e kufizon gjatësinëseri, por zgjedh maksimumin e mundshëm.
Algoritmi i renditjes:
- Leximi i sekuencës fillestare nga skedari f. Elementi i parë i marrë është shkruar në skedarin f1.
- Nëse hyrja tjetër plotëson kushtin e renditjes, shkruhet aty, nëse jo, atëherë në skedarin e dytë ndihmës f2.
- Në këtë mënyrë, të gjitha regjistrimet e skedarit burim shpërndahen dhe formohet një sekuencë e renditur në f1, e cila përcakton madhësinë aktuale të serisë.
- Skedarët f1 dhe f2 janë bashkuar.
- Cikli përsëritet.
Për shkak të madhësisë jo fikse të serisë, është e nevojshme të shënohet fundi i sekuencës me një karakter të veçantë. Prandaj, kur bashkohen, numri i krahasimeve rritet. Përveç kësaj, madhësia e një prej skedarëve ndihmës mund të jetë afër madhësisë së origjinalit.
Mesatarisht, bashkimi natyror është më efikas se bashkimi i thjeshtë me renditjen e jashtme.
Veçoritë e algoritmit
Kur krahasohen dy vlera identike, metoda ruan rendin e tyre origjinal, domethënë është e qëndrueshme.
Procesi i renditjes mund të ndahet me shumë sukses në fije të shumta.
Videoja demonstron qartë funksionimin e algoritmit të renditjes së bashkimit.
