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

Burbuļu kārtošana un ievietošanas 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. Ievietošanas kārtība ir arī kārtošanas algoritms, kas darbojas, ievietojot elementu ievades sarakstā pareizajā vietā sarakstā, kas jau ir sakārtots. Šis process tiek piemērots atkārtoti, līdz saraksts tiek kārtots.

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 ievietošanas kārtošana?

Ievietošanas kārtība ir vēl viens šķirošanas algoritms, kas darbojas, ievades sarakstā ievietojot elementu pareizajā pozīcijā sarakstā (kas jau ir sakārtots). Šis process tiek piemērots atkārtoti, līdz saraksts tiek kārtots. Ievietojot kārtošanu, šķirošana tiek veikta uz vietas. Tāpēc pēc algoritma astotās iterācijas pirmie saraksta i + 1 ieraksti tiks sakārtoti, bet pārējais saraksts tiks nešķirots. Katrā atkārtojumā pirmais elements nešķirotajā saraksta daļā tiks ņemts un ievietots pareizajā vietā saraksta sakārtotajā sadaļā. Ievietošanas kārtojumam vidējā gadījuma laika sarežģītība ir O (n2). Sakarā ar to ievietošanas kārtība nav piemērota arī lielu sarakstu šķirošanai.

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

Pat ja gan burbuļu kārtošanas, gan ievietošanas 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 ievietošanas kārtošana. 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. Ir arī iespraušanas veida variants, ko sauc par čaulas kārtojumu, kura laika sarežģītība ir O (n3 / 2), kas ļautu to praktiski izmantot. Turklāt ievietošanas kārtošana ir ļoti efektīva “gandrīz sakārtotu” sarakstu kārtošanai, salīdzinot ar burbuļu kārtošanu.