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šana | Apvienot šķirošanu |
|---|---|---|
| Masīva elementu sadalīšana | Elementu 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ība | O (n2) | O (n log n) |
| Darbojas labi | Mazāks masīvs | Darbojas 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ība | Mazāk | Vairāk |
| Efektivitāte | Neefektīva 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 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.
- Pirmais elements vai jebkurš izlases elements, kas izvēlēts kā atslēga, uzņemas taustiņu = A (1).
- “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;
- Konsekventi palieliniet "zemo" rādītāju ar vienu pozīciju, līdz (A [zems]> taustiņš).
- Pastāvīgi samaziniet rādītāju uz augšu ar vienu pozīciju, līdz (A [uz augšu] <= taustiņš).
- Ja uz augšu ir lielāks nekā zems A apmaiņas mezgls ar [A] [augšup].
- 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.
- 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.
- 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.
- 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ā.
- 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]).
- 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
- 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.
- Ā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).
- 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.
- Dažos gadījumos, piemēram, maziem datu kopumiem, ātrā kārtošana ir ātrāka par apvienošanu.
- 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.
- Sapludināšanas veids ir efektīvāks nekā ātrs.
- Ā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).
