Burbuļu kārtošana pret atlases kārtošanu
Burbuļu kārtošana ir kārtošanas algoritms, kas darbojas, atkārtoti kārtojot sarakstu, salīdzinot blakus esošo elementu pārus. Ja elementu pāris ir nepareizā secībā, tie tiek apmainīti, lai ievietotu tos pareizajā secībā. Šo pārvietošanos atkārto, līdz vairs nav nepieciešama mijmaiņas maiņa. Atlases kārtošana ir arī kārtošanas algoritms, kas sākas ar minimālā elementa atrašanu sarakstā un apmaiņu ar pirmo elementu. Šis process tiek atkārtots atlikušajā saraksta daļā, sakārtojot apmainītos elementus.
Kas ir burbuļu kārtošana?
Burbuļu kārtošana ir kārtošanas algoritms, kas darbojas, atkārtoti kārtojot sarakstu, salīdzinot blakus esošo elementu pārus. Ja elementu pāris ir nepareizā secībā, tie tiek apmainīti, lai ievietotu tos pareizajā secībā. Šī pārvietošanās tiek atkārtota, līdz vairs nav nepieciešami mijmaiņas darījumi (tas nozīmē, ka saraksts ir sakārtots). Tā kā mazākie elementi sarakstā nonāk augšpusē, kad virspusē iznāk burbulis, tam tiek piešķirts nosaukums burbuļu kārtošana. Burbuļu kārtošana ir ļoti vienkāršs kārtošanas algoritms, taču, kārtojot sarakstu ar n elementiem, tā vidējā gadījuma laika sarežģītība ir O(n2). Šī iemesla dēļ burbuļu kārtošana nav piemērota sarakstu kārtošanai ar lielu elementu skaitu. Taču tās vienkāršības dēļ burbuļu kārtošana tiek mācīta, ievadot algoritmus.
Kas ir atlases kārtošana?
Atlases kārtošana ir arī vēl viens kārtošanas algoritms, kas sākas ar minimālā elementa atrašanu sarakstā un apmaiņu ar pirmo elementu. Tad minimālais elements tiek atrasts no atlikušās saraksta daļas (no otrā elementa līdz pēdējam elementam sarakstā) un apmainīts ar otro elementu. Šo procesu atkārto atlikušajā saraksta daļā, sakārtojot apmainītos elementus. Tātad atlases kārtošanā jebkurā algoritma solī saraksts tiek sadalīts divās daļās, kur vienā daļā ir sakārtoti elementi, bet otrā daļā ir nešķiroti elementi. Algoritmam turpinoties, sakārtotais saraksts palielinās no kreisās puses uz labo. Atlases kārtošanai ir arī vidējā gadījuma laika sarežģītība O(n2). Tāpēc tas nav piemērots arī lielu sarakstu kārtošanai.
Kāda ir atšķirība starp burbuļu kārtošanu un atlases kārtošanu?
Lai gan burbuļu kārtošanas un atlases kārtošanas algoritmiem ir vidējā gadījuma laika sarežģītība O(n2), burbuļu kārtošana gandrīz visu laiku ir labāka par atlases kārtošanu. Tas ir saistīts ar mijmaiņas darījumu skaitu, kas nepieciešams abiem algoritmiem (burbuļu šķirošanai nepieciešams vairāk mijmaiņas darījumu). Bet burbuļu kārtošanas vienkāršības dēļ tā koda lielums ir ļoti mazs. Stabilitāte ir vēl viena atšķirība šajos divos algoritmos. Stabils kārtošanas algoritms ir kārtošanas algoritms, kas saglabā ierakstu secību, ja sarakstā ir elementi ar vienādu vērtību. Šajā ziņā atlases kārtošana nav stabils algoritms, savukārt burbuļu kārtošana ir stabils algoritms.
