Burbuļu kārtošana pret ievietošanas 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. Ievietošanas kārtošana ir arī kārtošanas algoritms, kas darbojas, ievietojot elementu ievades sarakstā pareizajā vietā sarakstā, kas jau ir sakārtots. Šis process tiek izmantots atkārtoti, līdz saraksts ir sakārtots.
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 ievietošanas kārtošana?
Ievietošanas kārtošana ir vēl viens kārtošanas algoritms, kas darbojas, ievietojot elementu ievades sarakstā pareizajā sarakstā (kas jau ir sakārtots). Šis process tiek izmantots atkārtoti, līdz saraksts ir sakārtots. Ievietošanas kārtošanā šķirošana tiek veikta uz vietas. Tāpēc pēc algoritma iterācijas pirmie i+1 ieraksti sarakstā tiks sakārtoti, bet pārējais saraksts tiks nešķirots. Katrā iterācijā pirmais elements saraksta nešķirotajā daļā tiks ņemts un ievietots pareizajā vietā sakārtotajā saraksta sadaļā. Ievietošanas kārtošanas vidējā gadījuma laika sarežģītība ir O(n2). Šī iemesla dēļ ievietošanas kārtošana nav piemērota arī lielu sarakstu kārtošanai.
Kāda ir atšķirība starp burbuļu kārtošanu un ievietošanas kārtošanu?
Lai gan burbuļu kārtošanas un ievietošanas kārtošanas algoritmiem ir vidējā gadījuma laika sarežģītība O(n2), burbuļu kārtošana gandrīz visu laiku pārspēj ievietošanas 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. Ir arī ievietošanas kārtošanas variants, ko sauc par čaulas šķirošanu, 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, lai kārtotu “gandrīz sakārtotus” sarakstus, salīdzinot ar burbuļu kārtošanu.
