Ieteicams, 2024

Redaktora Izvēle

Starpība starp burbuļu šķirošanu un atlasi Kārtot

Šķirošana ir viens no galvenajiem uzdevumiem datorprogrammās, kurās masīva elementi ir sakārtoti kādā noteiktā secībā. Šķirošana atvieglo meklēšanu. Bubble sort and Selection ir šķirošanas algoritmi, kurus var diferencēt, izmantojot metodes, ko tās izmanto šķirošanai. Bubble sort būtībā apmainās elementus, bet atlases kārtība veic šķirošanu, izvēloties elementu.

Vēl viena būtiska atšķirība starp abām ir tā, ka burbuļu šķirošana ir stabils algoritms, bet atlases kārtība ir nestabils algoritms. Tiek uzskatīts, ka algoritms ir stabils elementiem ar to pašu atslēgu, kas notiek tādā pašā secībā, kādā tie bija pirms šķirošanas sarakstā vai masīvā. Parasti visstabilākie un ātrākie algoritmi izmanto papildu atmiņu.

Salīdzinājuma diagramma

Salīdzināšanas pamatsBurbulis
Atlases kārtība
PamataBlakus esošais elements tiek salīdzināts un mainītsLielākais elements tiek atlasīts un mainīts ar pēdējo elementu (augošā secībā).
Labākais gadījuma laika sarežģītībaO (n)O (n 2 )
EfektivitāteNeefektīvaUzlabota efektivitāte, salīdzinot ar burbuļu šķirošanu
Stabils
MetodeApmaiņaIzvēle
ĀtrumsLēnsĀtri, salīdzinot ar burbuļu šķirošanu

Bubble Sort definīcija

Bubble sort ir vienkāršākais iteratīvais algoritms, kas darbojas, salīdzinot katru elementu vai elementu ar blakus esošo vienumu un nepieciešamības gadījumā tos mainot. Vienkārši runājot, tas salīdzina saraksta pirmo un otro elementu un maina to, ja vien tie nav konkrētā kārtībā. Līdzīgi, otrais un trešais elements tiek salīdzināti un mainīti, un šis salīdzinājums un pārnešana turpinās līdz saraksta beigām. Salīdzinājumu skaits pirmajā atkārtojumā ir n-1, kur n ir skaitļu elementi masīvā. Lielākais elements būtu pēc pirmā atkārtojuma n. Un pēc katras atkārtošanās salīdzinājumu skaits samazinās un pēdējā iterācijā notiek tikai viens salīdzinājums.

Šis algoritms ir vislēnākais šķirošanas algoritms. Bubble šķirnes labākais gadījuma sarežģītība (kad saraksts ir kārtībā) ir kārtībā n ( O (n) ), un sliktākajā gadījumā sarežģītība ir O (n2) . Labākajā gadījumā tas ir kārtībā n, jo tas tikai salīdzina elementus un nemaina tos. Šī metode prasa papildu vietu, lai saglabātu pagaidu mainīgo.

Atlases definīcija Kārtot

Atlases kārtība ir sasniegusi nedaudz labāku veiktspēju un ir efektīvāka par burbulīšu algoritmu. Pieņemsim, ka mēs vēlamies sakārtot masīvu augošā secībā, tad tā darbojas, atrodot lielāko elementu un apmainoties ar pēdējo elementu, un atkārtojiet šādu procesu apakšgrupās, līdz viss saraksts ir sakārtots.

Atlases kārtībā šķirotais un nešķirotais masīvs nedara nekādas atšķirības un patērē n2 ( O (n2) ) kārtību gan labākajā, gan sliktākajā gadījumā. Atlases kārtība ir ātrāka nekā Bubble sort.

Galvenās atšķirības starp burbuļu šķirošanu un atlasi Kārtot

  1. Burbuļu šķirojumā tiek salīdzināts katrs elements un tā blakus elements, ja nepieciešams. No otras puses, atlases kārtošana darbojas, izvēloties elementu un mainot konkrēto elementu ar pēdējo elementu. Izvēlētais elements var būt lielākais vai mazākais atkarībā no pasūtījuma, ti, augošā vai dilstošā secībā.
  2. Sliktākajā gadījumā sarežģītība ir vienāda abos algoritmos, ti, O (n2), bet labākā sarežģītība ir atšķirīga. Bubble sort notiek pēc n laika, bet atlases kārtība patērē n2 laika secību.
  3. Burbulis ir stabils algoritms, savukārt atlases kārtība ir nestabila.
  4. Atlases šķirošanas algoritms ir ātrs un efektīvs, salīdzinot ar burbuļu veidu, kas ir ļoti lēns un neefektīvs.

Secinājums

Bubble šķirošanas algoritms tiek uzskatīts par visvienkāršāko un neefektīvāko algoritmu, bet atlases šķirošanas algoritms ir efektīvs, salīdzinot ar burbuļu šķirošanu. Bubble sort arī patērē papildu vietu pagaidu mainīgā lieluma glabāšanai un prasa vairāk mijmaiņas darījumu.

Top