Atšķirība starp burbuļu kārtošanu un atlases kārtošanu

Burbuļu kārtošana vs atlases kārtošana

Burbuļa kārtošana ir šķirošanas algoritms, kas darbojas, atkārtoti izejot caur kārtojamo sarakstu, salīdzinot blakus esošos elementu pārus. Ja pāris elementu ir nepareizā secībā, tie tiek apmainīti, lai tos ievietotu pareizajā secībā. Šo šķērsošanu atkārto, līdz vairs nav vajadzīgi mijmaiņas darījumi. Atlases kārtošana ir arī kārtošanas algoritms, kas sākas ar saraksta minimālā elementa atrašanu un tā apmaiņu ar pirmo elementu. Šo procesu atkārto atlikušajā saraksta daļā, sakārtojot samainītos elementus.

Kas ir burbuļu kārtošana?

Burbuļa kārtošana ir šķirošanas algoritms, kas darbojas, atkārtoti izejot caur kārtojamo sarakstu, salīdzinot blakus esošos elementu pārus. Ja pāris elementu ir nepareizā secībā, tie tiek apmainīti, lai tos ievietotu pareizajā secībā. Šo šķērsošanu atkārto, līdz vairs nav vajadzīgi mijmaiņas darījumi (tas nozīmē, ka saraksts ir sakārtots). Tā kā mazāki saraksta elementi nonāk augšpusē, kad burbulis nonāk virspusē, tam tiek piešķirts nosaukums burbuļu kārtojums. Burbuļu kārtošana ir ļoti vienkāršs algoritms, taču, šķirojot sarakstu ar n elementiem, tā vidējā gadījuma laika sarežģītība ir O (n2). Tādēļ burbuļu kārtošana nav piemērota, lai kārtotu sarakstus ar lielu skaitu elementu. Bet, pateicoties vienkāršībai, algoritmu ievadīšanas laikā tiek mācīts burbuļu kārtojums.

Kas ir atlases kārtošana??

Atlases kārtošana ir arī vēl viens šķirošanas algoritms, kas sākas ar saraksta minimālā elementa atrašanu un apmaiņu ar pirmo elementu. Pēc tam minimālo elementu atrod no saraksta atlikušās daļas (no otrā elementa līdz pēdējam saraksta elementam) un apmaina ar otro elementu. Šo procesu atkārto atlikušajā saraksta daļā, sakārtojot samainītos elementus. Tātad atlases kārtošanā jebkurā algoritma posmā saraksts tiek sadalīts divās daļās, kur viena daļa satur sakārtotus elementus, bet otra - nešķirotus elementus. Turpinot algoritmu, sakārtotais saraksts palielinās no kreisās uz labo. Izlases veidam vidējā gadījuma laika sarežģītība ir arī O (n2). Tāpēc tas nav piemērots arī lielu sarakstu šķirošanai.

Kāda ir atšķirība starp burbuļu kārtošanu un atlases kārtošanu?

Kaut arī 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šanu gandrīz visu laiku pārspēj atlases kārtojums. Tas ir saistīts ar mijmaiņas darījumu skaitu, kas vajadzīgs abiem algoritmiem (burbuļu veidiem ir 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 šķirošanas algoritms ir šķirošanas algoritms, kas saglabā ierakstu secību, ja sarakstā ir elementi ar vienādu vērtību. Šajā ziņā atlases kārtība nav stabils algoritms, turpretī burbuļveida kārtojums ir stabils algoritms.