Sortiranje mjehurićima u odnosu na sortiranje odabirom
Bubble sortiranje je algoritam za sortiranje koji radi tako što se više puta prolazi kroz popis koji treba sortirati dok uspoređuje parove elemenata koji su susjedni. Ako je par elemenata u pogrešnom redoslijedu, oni se zamjenjuju kako bi se postavili u ispravnom redoslijedu. Ovaj obilazak se ponavlja sve dok više nisu potrebne daljnje zamjene. Sortiranje odabirom također je algoritam sortiranja koji počinje pronalaženjem minimalnog elementa na popisu i zamjenom s prvim elementom. Ovaj se postupak ponavlja za ostatak popisa postavljanjem zamijenjenih elemenata redom.
Što je Bubble Sort?
Bubble sortiranje je algoritam za sortiranje koji radi tako što se više puta prolazi kroz popis koji treba sortirati dok uspoređuje parove elemenata koji su susjedni. Ako je par elemenata u pogrešnom redoslijedu, oni se zamjenjuju kako bi se postavili u ispravnom redoslijedu. Ovaj obilazak se ponavlja sve dok više nisu potrebne daljnje zamjene (što znači da je lista sortirana). Budući da manji elementi na popisu dolaze na vrh kada mjehurić izlazi na površinu, dobio je naziv sortiranje mjehurića. Bubble sort je vrlo jednostavan algoritam za sortiranje, ali ima prosječnu složenost slučaja od O(n2) pri sortiranju popisa s n elemenata. Zbog toga sortiranje u obliku mjehurića nije prikladno za sortiranje popisa s velikim brojem elemenata. Ali zbog svoje jednostavnosti, sortiranje u obliku mjehurića uči se tijekom uvoda u algoritme.
Što je sortiranje odabirom?
Sortiranje odabirom također je još jedan algoritam sortiranja koji počinje pronalaženjem minimalnog elementa na popisu i njegovom zamjenom s prvim elementom. Tada se minimalni element pronalazi iz ostatka liste (od drugog elementa do posljednjeg elementa na listi) i mijenja s drugim elementom. Ovaj se postupak ponavlja za ostatak popisa postavljanjem zamijenjenih elemenata po redu. Dakle, u selekcijskom sortiranju, u bilo kojem koraku algoritma, lista je podijeljena na dva dijela gdje jedan dio sadrži sortirane elemente, a drugi dio sadrži nesortirane elemente. Kako algoritam napreduje, sortirani popis raste slijeva nadesno. Odabir vrste također ima prosječnu složenost slučaja od O(n2). Stoga također nije prikladan za sortiranje velikih popisa.
Koja je razlika između Bubble Sort i Selection Sort?
Iako i algoritmi sortiranja s mjehurićima i sortiranja odabirom imaju prosječnu složenost vremena slučaja od O(n2), sortiranje mjehurićima je gotovo uvijek bolje od sortiranja odabirom. To je zbog broja zamjena potrebnih dvama algoritmima (mjehurićima je potrebno više zamjena). Ali zbog jednostavnosti sortiranja u mjehurićima, njegova veličina koda je vrlo mala. Stabilnost je još jedna razlika u ova dva algoritma. Stabilni algoritam sortiranja je algoritam sortiranja koji zadržava redoslijed zapisa ako popis sadrži elemente s jednakom vrijednošću. U tom smislu sortiranje odabirom nije stabilan algoritam dok je sortiranje mjehurićima stabilan algoritam.
