Apvienošanas kārtošana ir viens no datorzinātņu pamatalgoritmiem, ko 1945. gadā izstrādāja izcilais matemātiķis Džons fon Neimans. Piedaloties Manhetenas projektā, Neimans saskārās ar nepieciešamību efektīvi apstrādāt milzīgus datu apjomus. Viņa izstrādātajā metodē tika izmantots princips "skaldi un valdi", kas ievērojami samazināja darbam nepieciešamo laiku.
Algoritma princips un izmantošana
Sapludināšanas kārtošanas metode tiek izmantota tādu struktūru kārtošanas problēmās, kurām ir noteikta piekļuve elementiem, piemēram, masīviem, sarakstiem, straumēm.
Apstrādes laikā sākotnējais datu bloks tiek sadalīts mazos komponentos, līdz vienam elementam, kas faktiski jau ir sakārtots saraksts. Pēc tam tas tiek samontēts pareizajā secībā.
Lai kārtotu noteikta garuma masīvu, ir nepieciešama tāda paša izmēra papildu atmiņas apgabals, kurā sakārtotais masīvs tiek apkopots pa daļām.
Šo metodi var izmantot, lai pasūtītu jebkuru salīdzināmu datu tipu, piemēram, ciparus vai virknes.
Apvienošana sakārtotasižeti
Lai saprastu algoritmu, sāksim tā analīzi no beigām – no sakārtoto bloku sapludināšanas mehānisma.
Iedomāsimies, ka mums ir divi jebkādā veidā sakārtoti skaitļu masīvi, kas ir jāapvieno savā starpā, lai kārtošana netiktu pārtraukta. Vienkāršības labad mēs sakārtosim skaitļus augošā secībā.
Elementārs piemērs: abi masīvi sastāv no viena elementa katrā.
int arr1={31}; int arr2={18};
Lai tos apvienotu, jāņem pirmā masīva nulles elements (neaizmirstiet, ka numerācija sākas no nulles) un otrā masīva nulles elements. Tie ir attiecīgi 31 un 18. Saskaņā ar šķirošanas nosacījumu skaitlim 18 jābūt pirmajā vietā, jo tas ir mazāks. Vienkārši salieciet ciparus pareizā secībā:
int rezultāts={18, 31};
Apskatīsim sarežģītāku piemēru, kur katrs masīvs sastāv no vairākiem elementiem:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
Apvienošanas algoritms sastāvēs no mazāku elementu secīgas salīdzināšanas un to ievietošanas iegūtajā masīvā pareizā secībā. Lai sekotu līdzi aktuālajiem indeksiem, ieviesīsim divus mainīgos – index1 un index2. Sākotnēji mēs tos iestatījām uz nulli, jo masīvi ir sakārtoti, un mazākie elementi atrodas sākumā.
int index1=0; int index2=0;
Soli pa solim uzrakstīsim visu sapludināšanas procesu:
- Ņemiet elementu ar indeksu1 no masīva arr1 un elementu ar indeksu2 no masīva arr2.
- Salīdzināt, izvēlieties mazāko no tiem un ievietojietiegūtais masīvs.
- Palieliniet mazākā elementa pašreizējo indeksu par 1.
- Turpiniet no pirmā soļa.
Pirmajā orbītā situācija izskatīsies šādi:
indekss1=0; indekss2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; indekss1++; rezultāts[0]=arr1[0]; // rezultāts=[2]
Otrajā pagriezienā:
indekss1=1; indekss2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; indekss2++; rezultāts[1]=arr2[0]; // rezultāts=[2, 5]
Trešais:
indekss1=1; indekss2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; indekss2++; rezultāts[2]=arr2[1]; // rezultāts=[2, 5, 6]
Un tā tālāk, līdz tiek iegūts pilnībā sakārtots masīvs: {2, 5, 6, 17, 21, 19, 30, 45}.
Ja tiek sapludināti dažāda garuma masīvi, var rasties zināmas grūtības. Ko darīt, ja viens no pašreizējiem indeksiem ir sasniedzis pēdējo elementu un otrajā masīvā vēl ir palikuši dalībnieki?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 solis indekss1=0, indekss2=0; 1 2 rezultāts={1, 2}; // 3 soļu indekss1=1, indekss2=1; 4 < 5 rezultāts={1, 2, 4}; //4 solis indekss1=2, indekss2=1 ??
Mainīgais indekss1 ir sasniedzis vērtību 2, bet masīvā arr1 nav elementa ar šo indeksu. Šeit viss ir vienkārši: vienkārši pārsūtiet atlikušos otrā masīva elementus uz iegūto, saglabājot to secību.
rezultāts={1, 2, 4, 5, 6, 7, 9};
Šī situācija mums norāda uz nepieciešamībusaskaņot pašreizējo pārbaudes indeksu ar sapludināmā masīva garumu.
Apvienot shēmu dažāda garuma sakārtotām secībām (A un B):
- Ja abu secību garums ir lielāks par 0, salīdziniet A[0] un B[0] un pārvietojiet mazāko uz buferi.
- Ja vienas no secībām garums ir 0, ņemiet atlikušos otrās secības elementus un, nemainot to secību, pārejiet uz bufera beigām.
Otrā posma īstenošana
Piemērs divu sakārtotu masīvu savienošanai Java ir sniegts tālāk.
int a1=jauns int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=jauns int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=jauns int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.garums-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++; } }
Šeit:
- a1 un a2 ir sākotnējie sakārtotie masīvi, kas jāapvieno;
- a3 - pēdējais masīvs;
- i un j ir pašreizējo elementu indeksi masīviem a1 un a2.
Pirmais un otrais if nosacījumi nodrošina, ka indeksi nepārsniedz masīva lielumu. Attiecīgi trešais un ceturtais nosacījumu bloks tiek pārvietots uz iegūto mazākā elementa masīvu.
Skaldi un valdi
Tātad, mēs esam iemācījušies apvienot sakārtotovērtību kolekcijas. Var teikt, ka sapludināšanas kārtošanas algoritma otrā daļa - pati sapludināšana - jau ir sakārtota.
Tomēr jums joprojām ir jāsaprot, kā no sākotnējā nešķirotā skaitļu masīva pāriet uz vairākiem sakārtotiem, kurus var apvienot.
Apskatīsim algoritma pirmo posmu un uzzināsim, kā atdalīt masīvus.
Tas nav grūti - sākotnējais vērtību saraksts tiek sadalīts uz pusēm, tad arī katra daļa tiek sadalīta un tā tālāk, līdz tiek iegūti ļoti mazi bloki.
Šādu minimālo elementu garums var būt vienāds ar vienu, tas ir, tie paši var būt sakārtots masīvs, taču tas nav obligāts nosacījums. Bloka lielums tiek noteikts iepriekš, un, lai to pasūtītu, var izmantot jebkuru piemērotu kārtošanas algoritmu, kas efektīvi darbojas ar maza izmēra masīviem (piemēram, ātrā kārtošana vai ievietošanas kārtošana).
Tas izskatās šādi.
// sākotnējais masīvs {34, 95, 10, 2, 102, 70}; // pirmais sadalījums {34, 95, 10} un {2, 102, 70}; // sekundes dalījums {34} un {95, 10} un {2} un {102, 70}
Iegūtos blokus, kas sastāv no 1-2 elementiem, ir ļoti viegli sakārtot.
Pēc tam jāapvieno jau sakārtotie mazie masīvi pa pāriem, saglabājot dalībnieku secību, ko jau esam iemācījušies darīt.
Pirmā posma īstenošana
Masīva rekursīvā sadalīšana ir parādīta zemāk.
void mergeSort(T a, long start, long finish) { long split; ja(sākums < finišs) { sadalīšana=(sākums + finišs)/2; mergeSort(a, sākums, sadalīt); mergeSort(a, sadalīt+1, pabeigt); sapludināt(a, sākums, sadalīšana, finišs); } }
Kas notiek šajā kodā:
-
Funkcija mergeSort iegūst sākotnējo masīvu
a
un kārtojamā reģiona kreisās un labās robežas (indeksi sākas un
- finish).
-
Ja šīs sadaļas garums ir lielāks par vienu (
sākums < finišs
), tad tā tiek sadalīta divās daļās (pēc indeksa
- split), un katrs tiek kārtots rekursīvi.
-
Rekursīvās funkcijas izsaukumā kreisajai pusei tiek nodots diagrammas sākuma indekss un indekss
split
. Labajai daļai attiecīgi sākums būs
- (split + 1), bet beigas būs sākotnējās sadaļas pēdējais rādītājs.
-
Funkcija
merge
iegūst divas sakārtotas secības (
a[sākt]…a[split]
un
- a[sadalīt +1]…a[finish]) un apvieno tos kārtošanas secībā.
Apvienošanas funkcijas mehānika ir apspriesta iepriekš.
Algoritma vispārīgā shēma
Sapludināšanas kārtošanas masīva metode sastāv no diviem lieliem soļiem:
- Sadaliet nešķiroto sākotnējo masīvu mazos gabaliņos.
- Savāc tos pa pāriem, ievērojot šķirošanas likumu.
Liels un sarežģīts uzdevums tiek sadalīts daudzos vienkāršos, kas tiek atrisināti secīgi, tādējādi iegūstot vēlamo rezultātu.
Metodes novērtējums
Apvienošanas kārtošanas sarežģītību laikā nosaka sadalītā koka augstumsalgoritmu un ir vienāds ar elementu skaitu masīvā (n) reizināts ar tā logaritmu (log n). Šādu aprēķinu sauc par logaritmisko.
Tā ir gan metodes priekšrocība, gan trūkums. Tā darbības laiks nemainās pat sliktākajā gadījumā, kad sākotnējais masīvs tiek sakārtots apgrieztā secībā. Tomēr, apstrādājot pilnībā sakārtotus datus, algoritms nenodrošina laika pieaugumu.
Ir arī svarīgi ņemt vērā sapludināšanas kārtošanas metodes atmiņas izmaksas. Tie ir vienādi ar oriģinālās kolekcijas lielumu. Šajā papildus piešķirtajā apgabalā no daļām tiek salikts sakārtots masīvs.
Algoritma ieviešana
Pascal sapludināšanas kārtošana ir parādīta zemāk.
Procedure MergeSort(nosaukums: virkne; var f: teksts); Var a1, a2, s, i, j, kol, tmp: vesels skaitlis; f1, f2: teksts; b: Būla vērtība Begincol:=0; Piešķirt(f, vārds); atiestatīt(f); Lai gan tas nav EOF(f), sākas lasīšana (f, a1); inc(col); beigas; aizvērt(f); Assign(f1, '{1. palīgfaila nosaukums}'); Assign(f2, '{2. palīgfaila nosaukums}'); s:=1; Kamēr (s<kol) sāciet Reset(f); pārrakstīt(f1); pārrakstīt(f2); Ja i:=1 līdz kol div 2, sāciet Read(f, a1); Write(f1, a1, ' '); beigas; Ja (kol div 2) mod s0, tad sākas tmp:=kol div 2; Kamēr tmp mod s0 sākas Read(f, a1); Write(f1, a1, ' '); inc(tmp); beigas; beigas; Lai gan tas nav EOF(f), sākas Read(f, a2); Write(f2, a2, ' '); beigas; aizvērt(f); aizvērt(f1); aizvērt(f2); pārrakstīt(f); atiestatīt(f1); atiestatīt(f2); Lasīt(f1, a1); Lasīt(f2, a2); Kamēr (nevis EOF(f1)) un (ne EOF(f2)) sākas i:=0; j:=0; b:=true; Kamēr (b) un (nevis EOF(f1)) un (nevis EOF(f2)) sākas Ja (a1<a2), tad sākasWrite(f, a1, ' '); Lasīt(f1, a1); inc(i); End else begin Write(f, a2, ' '); Lasīt(f2, a2); inc(j); beigas; Ja (i=s) vai (j=s), tad b:=false; beigas; Ja nav b, tad sāciet While (i<s) un (nevis EOF(f1)) sāciet Write(f, a1, ' '); Lasīt(f1, a1); inc(i); beigas; Kamēr (j<s) un (nevis EOF(f2)) sākas Write(f, a2, ' '); Lasīt(f2, a2); inc(j); beigas; beigas; beigas; Lai gan tas nav EOF(f1), sākas tmp:=a1; Lasīt(f1, a1); Ja ne EOF(f1), tad Write(f, tmp, ' ') else Write(f, tmp); beigas; Lai gan tas nav EOF(f2), sākas tmp:=a2; Lasīt(f2, a2); Ja ne EOF(f2), tad Write(f, tmp, ' ') else Write(f, tmp); beigas; aizvērt(f); aizvērt(f1); aizvērt(f2); s:=s2; beigas; Dzēst(f1); Dzēst(f2); Beigas;
Vizuāli algoritma darbība izskatās šādi (augšā - nesakārtota secība, apakšā - sakārtota).
Ārējo datu kārtošana
Ļoti bieži ir nepieciešams kārtot dažus datus, kas atrodas datora ārējā atmiņā. Dažos gadījumos tiem ir iespaidīgs izmērs, un tos nevar ievietot RAM, lai atvieglotu piekļuvi tiem. Šādos gadījumos tiek izmantotas ārējās šķirošanas metodes.
Nepieciešamība piekļūt ārējiem datu nesējiem samazina apstrādes laika efektivitāti.
Darba sarežģītība ir tāda, ka algoritms vienlaikus var piekļūt tikai vienam datu straumes elementam. Un šajā gadījumā vienu no labākajiem rezultātiem parāda sapludināšanas kārtošanas metode, kas var salīdzināt divu failu elementus secīgi vienu pēc otra.
Notiek datu lasīšana noārējais avots, to apstrāde un ierakstīšana gala failā tiek veikta sakārtotos blokos (sērijās). Atbilstoši darba veidam ar pasūtīto sēriju izmēriem ir divi šķirošanas veidi: vienkārša un dabiska sapludināšana.
Vienkārša sapludināšana
Ar vienkāršu sapludināšanu sērijas garums tiek fiksēts.
Tādējādi sākotnējā nešķirotajā failā visas sērijas sastāv no viena elementa. Pēc pirmā soļa izmērs palielinās līdz diviem. Nākamais - 4, 8, 16 un tā tālāk.
Tas darbojas šādi:
- Avota fails (f) ir sadalīts divos palīgfailos - f1, f2.
- Tie atkal tiek sapludināti vienā failā (f), bet tajā pašā laikā visi elementi tiek salīdzināti pa pāriem un veido pārus. Sērijas lielums šajā darbībā kļūst par diviem.
- 1. darbība tiek atkārtota.
- 2. darbība tiek atkārtota, bet jau pasūtītie 2 tiek apvienoti, veidojot sakārtotus 4.
- Cilpa turpinās, palielinot sēriju katrā iterācijā, līdz viss fails ir sakārtots.
Kā zināt, ka ārējā kārtošana ar vienkāršu sapludināšanu ir pabeigta?
- jaunas sērijas garums (pēc sapludināšanas) ne mazāks par kopējo elementu skaitu;
- atlikusi tikai viena sērija;
- Palīgfails f2 tika atstāts tukšs.
Vienkāršas sapludināšanas trūkumi ir šādi: tā kā izpildes garums ir fiksēts katrā sapludināšanas gājienā, daļēji sakārtotu datu apstrāde prasīs tikpat ilgu laiku kā pilnīgi nejaušu datu apstrāde.
Dabiskā saplūšana
Šī metode neierobežo garumusēriju, bet izvēlas maksimāli iespējamo.
Kārtošanas algoritms:
- Sākotnējās secības nolasīšana no faila f. Pirmais saņemtais elements tiek ierakstīts failā f1.
- Ja nākamais ieraksts apmierina kārtošanas nosacījumu, tas tiek ierakstīts tur, ja nē, tad uz otro palīgfailu f2.
- Šādā veidā tiek izplatīti visi avota faila ieraksti, un f1 tiek veidota sakārtota secība, kas nosaka pašreizējo sērijas lielumu.
- Faili f1 un f2 ir apvienoti.
- Cikls atkārtojas.
Sērijas nefiksētā izmēra dēļ secības beigas ir nepieciešams atzīmēt ar speciālo rakstzīmi. Tāpēc, apvienojot, salīdzinājumu skaits palielinās. Turklāt viena papildu faila izmērs var būt tuvu oriģināla izmēram.
Vidēji dabiskā sapludināšana ir efektīvāka nekā vienkārša sapludināšana ar ārēju kārtošanu.
Algoritma funkcijas
Salīdzinot divas identiskas vērtības, metode saglabā to sākotnējo secību, tas ir, tā ir stabila.
Šķirošanas procesu var ļoti veiksmīgi sadalīt vairākos pavedienos.
Videoklipā skaidri parādīta sapludināšanas kārtošanas algoritma darbība.
