Atšķirība starp burbuļu kārtošanu un atlases kārtošanu
Saturs
Kārtošana ir viens no galvenajiem uzdevumiem datorprogrammās, kurā masīva elementi ir sakārtoti noteiktā secībā. Kārtošana atvieglo meklēšanu. Burbuļu kārtošana un atlases kārtošana ir šķirošanas algoritmi, kurus var diferencēt, izmantojot metodes, kuras viņi izmanto šķirošanai. Burbuļu šķirošana būtībā apmainās ar elementiem, savukārt atlases kārtošana veic šķirošanu, atlasot elementu.
Vēl viena būtiska atšķirība starp abām ir tāda, ka burbuļu kārtošana ir stabils algoritms, savukārt atlases kārtojums ir nestabils algoritms. Algoritms tiek uzskatīts par vienmērīgu elementu ar vienu un to pašu atslēgu parādīšanos tādā pašā secībā, kā tie bija pirms šķirošanas sarakstā vai masīvā. Parasti visstabilākie un ātrākie algoritmi izmanto papildu atmiņu.
- Salīdzināšanas tabula
- Definīcija
- Galvenās atšķirības
- Secinājums
Salīdzināšanas tabula
Salīdzināšanas pamats | Burbulis kārtot | Atlases kārtošana |
---|---|---|
Pamata | Blakus esošais elements tiek salīdzināts un apmainīts | Tiek izvēlēts lielākais elements un apmainīts ar pēdējo elementu (augošā secībā). |
Labākā gadījuma laika sarežģītība | O (n) | O (n2 ) |
Efektivitāte | Neefektīva | Uzlabota efektivitāte salīdzinājumā ar burbuļu kārtošanu |
Stabils | Jā | Nē |
Metode | Apmainās | Atlase |
Ātrums | Lēns | Ātri salīdzinājumā ar burbuļu kārtošanu |
Burbuļu kārtojuma definīcija
Burbulis kārtot ir vienkāršākais iteratīvais algoritms, kas darbojas, salīdzinot katru vienumu vai elementu ar blakus esošo vienumu un vajadzības gadījumā tos apmainot. Vienkāršiem vārdiem sakot, tas salīdzina pirmo un otro saraksta elementu un apmaina to, ja vien tie neatbilst noteiktai kārtībai. Līdzīgi tiek salīdzināts un apmainīts otrais un trešais elements, un šī salīdzināšana un apmaiņa turpinās līdz saraksta beigām. Salīdzinājumu skaits pirmajā iterācijā ir n-1, kur n ir skaitlis elementi masīvā. Pēc pirmās iterācijas lielākais elements būtu n. Pozīcijā. Pēc katras iterācijas salīdzinājumu skaits samazinās, un beidzot iterācija notiek tikai vienā.
Šis algoritms ir vislēnākais šķirošanas algoritms. Burbuļa veida labākā gadījuma sarežģītība (kad saraksts ir kārtībā) ir kārtas n (O (n)), un vissliktākais gadījums ir sarežģīts O (n2). Labākajā gadījumā tas ir secībā n, jo tas tikai salīdzina elementus un tos nemaina. Šis paņēmiens prasa arī papildu vietu pagaidu mainīgā lieluma glabāšanai.
Atlases kārtošanas definīcija
Atlases kārtošana ir sasniedzis nedaudz labāku sniegumu un ir efektīvāks nekā burbuļu kārtošanas algoritms. Pieņemsim, ka mēs vēlamies sakārtot masīvu augošā secībā, tad tas funkcionē, atrodot lielāko elementu un apmainot to ar pēdējo elementu, un atkārtojiet šo procesu apakšmasīvos, līdz viss saraksts ir sakārtots.
Atlasot kārtošanu, sakārtotais un nešķirotais masīvs neko nemaina un patērē n secību2 (O (n2)) gan labākajā, gan sliktākajā gadījumā. Kārtošana pēc atlases ir ātrāka nekā burbuļa kārtošana.- Burbuļu secībā katrs elements un tam blakus esošais elements tiek salīdzināti un, ja nepieciešams, apmainīti. No otras puses, atlases kārtošana darbojas, atlasot elementu un apmainot šo konkrēto elementu ar pēdējo elementu. Atlasītais elements varētu būt lielākais vai mazākais atkarībā no pasūtījuma, t.i., augoši vai dilstoši.
- Sliktākā gadījuma sarežģītība abos algoritmos ir vienāda, t.i., O (n2), bet vislabākā sarežģītība ir atšķirīga. Burbuļu šķirošana notiek n laika secībā, turpretī atlases kārtošana patērē n pakāpi2 laiks.
- Burbuļu kārtošana ir stabils algoritms, turpretī atlases kārtība ir nestabila.
- Atlases kārtošanas algoritms ir ātrs un efektīvs, salīdzinot ar burbuļu kārtošanu, kas ir ļoti lēns un neefektīvs.
Secinājums
Burbuļu kārtošanas algoritms tiek uzskatīts par vienkāršāko un neefektīvāko algoritmu, bet atlases kārtošanas algoritms ir efektīvs, salīdzinot ar burbuļu kārtošanu. Burbuļu šķirošana arī patērē papildu vietu pagaidu mainīgā lieluma glabāšanai, un tai vajadzīgi vairāk mijmaiņas darījumu.