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 pamats | Burbulis | Atlases kārtība |
|---|---|---|
| Pamata | Blakus esošais elements tiek salīdzināts un mainīts | Lielākais elements tiek atlasīts un mainīts ar pēdējo elementu (augošā secībā). |
| Labākais gadījuma laika sarežģītība | O (n) | O (n 2 ) |
| Efektivitāte | Neefektīva | Uzlabota efektivitāte, salīdzinot ar burbuļu šķirošanu |
| Stabils | Jā | Nē |
| Metode | Apmaiņa | Izvēle |
| Ātrums | Lē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.
Galvenās atšķirības starp burbuļu šķirošanu un atlasi Kārtot
- 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ā.
- 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.
- Burbulis ir stabils algoritms, savukārt atlases kārtība ir nestabila.
- 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.
