Ieteicams, 2021

Redaktora Izvēle

Starpība starp ātrās kārtošanas un apvienošanas kārtību

Ātrās kārtošanas un apvienošanas algoritmi ir balstīti uz sadalīšanas un iekarošanas algoritmu, kas darbojas diezgan līdzīgā veidā. Iepriekšējā atšķirība starp ātru un sapludinātu šķirni ir tāda, ka ātrā kārtībā šķirošanai izmanto pagrieziena elementu. No otras puses, šķirot šķirošanu neizmanto pivot elementu šķirošanas veikšanai.

Abas šķirošanas metodes, ātra kārtošana un apvienošana tiek veidotas uz sadalīšanas un iekarošanas metodes, kurā elementu kopa ir sadalīta un pēc tam apvienota pēc pārkārtošanas. Ātra kārtība parasti prasa vairāk salīdzinājumu nekā apvienot, lai šķirotu lielu elementu kopumu.

Salīdzinājuma diagramma

Salīdzināšanas pamatsĀtra kārtošanaApvienot šķirošanu
Masīva elementu sadalīšanaElementu saraksta sadalīšana ne vienmēr ir sadalīta uz pusi.Array vienmēr ir sadalīta uz pusēm (n / 2).
Sliktākā gadījuma sarežģītībaO (n2)O (n log n)
Darbojas labiMazāks masīvsDarbojas ar naudas sodu jebkura veida masīvā.
ĀtrumsĀtrāk nekā citi šķirošanas algoritmi maziem datu kopumiem.Pastāvīgs ātrums visu veidu datu kopās.
Papildu uzglabāšanas vietas prasībaMazākVairāk
EfektivitāteNeefektīva lielākiem blokiem.Efektīvāks.
Šķirošanas metodeIekšējaisĀrējais

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

Ātra kārtošana tiek plaši izmantota šķirošanas algoritms, jo tā ir ātra īsajiem blokiem. Elementu kopums tiek atkārtoti sadalīts daļās, līdz nav iespējams to sadalīt tālāk. Ātra kārtība ir arī pazīstama kā nodalījuma apmaiņa . Tajā tiek izmantots galvenais elements (pazīstams kā pivots) elementu sadalīšanai. Viens nodalījums satur tos elementus, kas ir mazāki par galveno elementu. Citā nodalījumā ir tie elementi, kas ir lielāki par galveno elementu. Elementi tiek sakārtoti rekursīvi.

Pieņemsim, ka A ir masīvs A [1], A [2], A [3], …… .., A [n] no n numuriem, kas ir sakārtoti. Ātrās kārtošanas algoritms sastāv no šādiem soļiem.

  1. Pirmais elements vai jebkurš izlases elements, kas izvēlēts kā atslēga, uzņemas taustiņu = A (1).
  2. “Zems” rādītājs atrodas otrajā un “augšup” rādītājs ir novietots masīva pēdējā elementā, ti, zems = 2 un augšup = n;
  3. Konsekventi palieliniet "zemo" rādītāju ar vienu pozīciju, līdz (A [zems]> taustiņš).
  4. Pastāvīgi samaziniet rādītāju uz augšu ar vienu pozīciju, līdz (A [uz augšu] <= taustiņš).
  5. Ja uz augšu ir lielāks nekā zems A apmaiņas mezgls ar [A] [augšup].
  6. Atkārtojiet 3.4. Un 5. soli, līdz 5. solī esošais stāvoklis neizdodas (ti, līdz <= zems), tad pārslēdziet A [uz augšu] ar taustiņu.
  7. Ja taustiņa kreisie elementi ir mazāki par atslēgu, un galvenie elementa elementi ir lielāki par atslēgu, tad masīvs tiek sadalīts divās apakšgrupās.
  8. Iepriekš aprakstītā procedūra tiek atkārtoti piemērota apakšjoslām, līdz viss masīvs ir sakārtots.

Priekšrocības un trūkumi

Tam piemīt laba vidējā gadījumu uzvedība. Ātrās kārtības sarežģītības laiks ir labs, tas ir, tas ir ātrāks par algoritmiem, piemēram, burbuļu šķirošanu, ievietošanas kārtību un atlasi. Tomēr tas ir sarežģīts un ļoti rekursīvs, tāpēc tas nav piemērots lieliem masīviem.

Sapludināšanas veida definīcija

Sapludināšanas veids ir ārējs algoritms, kas balstās arī uz dalīšanas un iekarošanas stratēģiju. Elementi tiek sadalīti apakšgrupās (n / 2) atkal un atkal, līdz paliek tikai viens elements, kas būtiski samazina šķirošanas laiku. Tā izmanto papildu krātuvi, lai uzglabātu papildu masīvu. Apvienot šķirošanu izmanto trīs masīvus, kur divi tiek izmantoti katras puses glabāšanai, un trešais tiek izmantots, lai saglabātu galīgo šķiroto sarakstu. Pēc tam katra masīva tiek sakārtota rekursīvi. Beidzot, apakšgrupas tiek apvienotas, lai padarītu to masīva n elementa lielumu. Sarakstā vienmēr ir sadalīti tikai puse (n / 2), kas atšķiras no ātras kārtības.

Ļaujiet A būt šķirotam elementu skaitam, kas jāšķiro A [1], A [2], ………, A [n]. Sapludināšanas secība atbilst dotajiem soļiem.

  1. Sadaliet masīvu A aptuveni n / 2 šķirotajā apakšgrupā ar 2, kas nozīmē, ka elementi (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]) (A [n-1], A [n]) apakšgrupām jābūt sakārtotajā secībā.
  2. Apvienojiet katru pāru pāru, lai iegūtu sarakstu ar sakārtotām apakšgrupām ar izmēru 4; apakšgrupu elementi ir arī sakārtoti secībā (A [1], A [2], A [3], A [4], ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……, (A [n-3], A [n-2], A [n-1], A [n]).
  3. 2. solis tiek atkārtoti veikts, līdz ir tikai viena sakārtota masīva ar izmēru n.

Priekšrocības un trūkumi

Sapludināšanas algoritms darbojas tieši tādā pašā un precīzā veidā, neatkarīgi no šķirošanā iesaistīto elementu skaita. Tas darbojas arī ar lielu datu kopu. Tomēr tā patērē lielāku atmiņas daļu.

Galvenās atšķirības starp ātru šķirošanu un sapludināšanu

  1. Sapludināšanas secībā masīvs jāsadala tikai divās daļās (ti, n / 2). Ātrā kārtībā nav nekāda piespiedu sadalīt sarakstu vienādos elementos.
  2. Ātrās kārtas sliktākajā gadījumā sarežģītība ir O (n2), jo vissliktākajā stāvoklī tas ir daudz vairāk salīdzināms. Turpretī apvienot šķirnei ir tāds pats sliktākais gadījums un vidējie gadījuma sarežģījumi, tas ir, O (n log n).
  3. Sapludināšanas veids var darboties labi jebkura veida datu kopās, neatkarīgi no tā, vai tas ir liels vai mazs. Gluži pretēji, ātrās šķirnes nevar strādāt ar lielām datu kopām.
  4. Dažos gadījumos, piemēram, maziem datu kopumiem, ātrā kārtošana ir ātrāka par apvienošanu.
  5. Lai apvienotu palīgtīklus, sapludināšanas kārtībai ir nepieciešama papildu atmiņa. No otras puses, ātrajai kārtībai nav nepieciešama daudz vietas papildu uzglabāšanai.
  6. Sapludināšanas veids ir efektīvāks nekā ātrs.
  7. Ātra kārtošana ir iekšēja šķirošanas metode, kurā dati, kas ir jāklasificē, tiek regulēti galvenajā atmiņā. Un otrādi, sapludināšanas veids ir ārējā šķirošanas metode, kurā datus, kas ir jāklasificē, nevar ievietot atmiņā vienlaicīgi, un daži ir jāglabā palīg atmiņā.

Secinājums

Ātra kārtība ir ātrāks gadījums, bet dažās situācijās tas ir neefektīvs, kā arī veic daudz salīdzinājumu, salīdzinot ar apvienošanu. Lai gan apvienošanas šķirnei ir vajadzīgs mazāks salīdzinājums, tai ir nepieciešama papildu atmiņa 0 (n), lai saglabātu papildu masīvu, savukārt ātrai kārtošanai ir vajadzīgs O (log n).

Top