Saturs

• Salīdzināšanas tabula
• Ātrās kārtošanas definīcija
• Apvienošanas kārtības definīcija
• Secinājums

Ātrās kārtošanas un apvienošanas algoritmi ir balstīti uz dalīšanas un iekarošanas algoritmu, kas darbojas diezgan līdzīgi. Iepriekš atšķirība starp ātro un apvienoto šķirošanu ir tā, ka ātrajā šķirošanā šķirošanas elements tiek izmantots šarnīra elements. No otras puses, apvienojot šķirot, šķirošanai netiek izmantots šarnīra elements.

Gan šķirošanas paņēmieni, gan ātrā kārtošana, gan apvienošanas kārtība ir veidoti pēc dalīšanas un iekarošanas metodes, kurā elementu komplekts tiek sadalīts un pēc pārkārtošanas apvienots. Ātrajai šķirošanai parasti ir nepieciešams vairāk salīdzinājumu nekā apvienošanai, lai kārtotu lielu elementu kopu.

1. 1. Salīdzināšanas tabula
   2. Definīcija
   3. Galvenās atšķirības
   4. Secinājums

Salīdzināšanas tabula

Salīdzināšanas pamats	Ātra kārtošana	Apvienot šķirot
Elementu sadalīšana masīvā	Elementu saraksta sadalīšana ne vienmēr ir sadalīta uz pusēm.	Masīvs vienmēr tiek sadalīts uz pusēm (n / 2).
Sliktākā gadījuma sarežģītība	O (n2)	O (n log n)
Labi darbojas	Mazāks masīvs	Lieliski darbojas jebkura veida masīvā.
Ātrums	Ātrāk nekā citi mazas datu kopas šķirošanas algoritmi.	Pastāvīgs ātrums visa veida datu kopās.
Papildu uzglabāšanas vietas prasība	Mazāk	Vairāk
Efektivitāte	Neefektīvs lielākiem blokiem.	Efektīvāks.
Šķirošanas metode	Iekšējais	Ārējais

Ātrās kārtošanas definīcija

Ātra kārtošana tiek plaši izmantots kārtošanas algoritms, jo tas ir ātrs īsiem masīviem. Elementu komplekts atkārtoti tiek sadalīts daļās, līdz to nav iespējams sadalīt tālāk. Ātro kārtošanu sauc arī par nodalījuma apmaiņas kārtot. Elementu sadalīšanai tiek izmantots galvenais elements (pazīstams kā šarnīrsavienojums). Vienā nodalījumā ir elementi, kas ir mazāki par galveno elementu. Citā nodalījumā ir elementi, kas ir lielāki par galveno elementu. Elementi tiek sakārtoti rekursīvi.

Pieņemsim, ka A ir masīvs A, A, A, …… .., A no n skaita, kas ir jāsakārto. Ātrās kārtošanas algoritms sastāv no šādām darbībām.

1. Pirmais elements vai jebkurš izlases elements, kas izvēlēts kā atslēga, pieņem taustiņu = A (1).
2. “Zemais” rādītājs tiek novietots otrajā, un “uz augšu” rādītājs ir novietots pie masīva pēdējā elementa, t.i., zems = 2 un uz augšu = n;
3. Konsekventi palieliniet “zemo” rādītāju par vienu pozīciju, līdz (taustiņš A>).
4. Pastāvīgi samaziniet rādītāju “uz augšu” par vienu pozīciju, līdz (A <= taustiņš).
5. Ja augšup ir lielāks par zemu apmaiņu A ar A.
6. Atkārtojiet 3.4. Un 5. darbību, līdz 5. solī esošais nosacījums neizdodas (t.i., augšup <= zems), pēc tam apmainiet A ar atslēgu.
7. Ja atslēgas elementi pa kreisi ir mazāki par atslēgu un atslēgas labās puses elementi ir lielāki par atslēgu, tad masīvs tiek sadalīts divos apakšblokos.
8. Iepriekš aprakstītā procedūra tiek atkārtoti piemērota apakšmatricām, līdz viss masīvs ir sakārtots.

   

   
   

Priekšrocības un trūkumi

Tam ir laba vidējā izturēšanās pret lietu. Ātrās kārtošanas laika sarežģītība ir laba, tas ir, tas ir ātrāks nekā algoritmi, piemēram, burbuļu kārtošana, ievietošanas kārtība un atlases kārtošana. Tomēr tas ir sarežģīts un ļoti rekursīvs, tāpēc tas nav piemērots lieliem blokiem.

Apvienošanas kārtības definīcija

Apvienot šķirot ir ārējs algoritms, kura pamatā ir arī dalīšanas un iekarošanas stratēģija. Elementi atkal un atkal tiek sadalīti apakšmasīvos (n / 2), līdz ir palicis tikai viens elements, kas ievērojami samazina šķirošanas laiku. Papildu masīva uzglabāšanai tas izmanto papildu krātuvi. Apvienot kārtošanu izmanto trīs masīvus, kur katras puses glabāšanai tiek izmantoti divi, bet trešo - galīgā sakārtotā saraksta glabāšanai. Pēc tam katrs masīvs tiek sakārtots rekursīvi. Beidzot apakšblāni tiek apvienoti, lai masīva n izmērs būtu n. Saraksts vienmēr ir sadalīts tikai uz pusēm (n / 2), kas atšķiras no ātras kārtošanas.

Ļaujiet A ir n kārtojamo elementu n masīvs, A, A, ………, A. Apvienošanas kārtība seko norādītajām darbībām.

1. Sadalīt masīvu A aptuveni n / 2 sakārtotā pakārtotā masīvā ar 2, kas nozīmē, ka elementiem (A, A), (A, A), (A, A), (A, A) apakšblokos jābūt jābūt sakārtotā secībā.
2. Apvieno katru pāru pāri, lai iegūtu sakārtoto apakšpamatņu sarakstu ar izmēru 4; elementi apakšblāzmās ir arī sakārtoti (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. 2. darbību atkārto atkārtoti, līdz ir tikai viens sakārtots masīvs ar n lielumu.

   

Priekšrocības un trūkumi

Apvienošanas kārtošanas algoritms darbojas tieši tāpat un precīzi neatkarīgi no šķirošanā iesaistīto elementu skaita. Tas darbojas labi pat ar lielu datu kopu. Tomēr tas patērē lielāku atmiņas daļu.

1. Apvienojot, masīvs jāsadala tikai divās daļās (t.i., n / 2). Pretstatā ātrajai kārtībai, nav nekāda spiesta sadalīt sarakstu vienādos elementos.
2. Ātrās šķirošanas sliktākais gadījums ir O (n²), jo sliktākajā stāvoklī tas prasa daudz vairāk salīdzinājumu. Turpretī apvienošanas kārtībai ir tāda pati sliktākā un vidējā gadījuma sarežģītība, tas ir, O (n log n).
3. Apvienotā kārtošana var labi darboties jebkura veida datu kopās neatkarīgi no tā, vai tās ir lielas vai mazas. Tieši pretēji, ātrā šķirošana nevar labi darboties ar lielām datu kopām.
4. Dažos gadījumos, piemēram, mazām datu kopām, ātrā kārtošana ir ātrāka nekā apvienošana.
5. Sapludināšanai ir nepieciešama papildu vieta, lai saglabātu papildu masīvus. No otras puses, ātrajai šķirošanai nav nepieciešams daudz vietas papildu krātuvei.
6. Apvienot kārtošana ir efektīvāka nekā ātrā kārtošana.
7. Ātrā šķirošana ir iekšējās šķirošanas metode, kurā kārtojamie dati vienlaikus tiek koriģēti galvenajā atmiņā. Un otrādi, sapludināšanas kārtība ir ārēja šķirošanas metode, kurā sakārtojamos datus nevar vienlaikus ievietot atmiņā, un daži no tiem jāpatur palīg atmiņā.

Secinājums

Ātrās šķirošanas gadījumi ir ātrāki, bet dažās situācijās ir neefektīvi, kā arī daudz salīdzina, salīdzinot ar apvienošanas veidu. Lai gan apvienošanai ir nepieciešams mazāks salīdzinājums, tai nepieciešama papildu atmiņas telpa 0 (n), lai saglabātu papildu masīvu, savukārt ātrajai šķirošanai ir nepieciešama vieta O (log n).