Mjehuričasto sortiranje vs sortiranje odabirom
Mjehuričasto sortiranje je algoritam za sortiranje koji radi tako što prolazi kroz listu koja se više puta sortira dok poredi parove susjednih elemenata. Ako je par elemenata u pogrešnom redoslijedu, oni se zamjenjuju kako bi bili postavljeni u ispravnom redoslijedu. Ovo kretanje se ponavlja sve dok više ne budu potrebne zamjene. Sortiranje odabirom je također algoritam sortiranja, koji počinje pronalaženjem minimalnog elementa na listi i zamjenom sa prvim elementom. Ovaj proces se ponavlja za ostatak liste stavljanjem zamijenjenih elemenata u red.
Šta je Bubble Sort?
Mjehuričasto sortiranje je algoritam za sortiranje koji radi tako što prolazi kroz listu koja se više puta sortira dok poredi parove susjednih elemenata. Ako je par elemenata u pogrešnom redoslijedu, oni se zamjenjuju kako bi bili postavljeni u ispravnom redoslijedu. Ovo kretanje se ponavlja sve dok više ne budu potrebne zamjene (što znači da je lista sortirana). Pošto manji elementi na listi dolaze do vrha kada balon izbija na površinu, dato mu je ime sortiranje mehurića. Bubble sortiranje je vrlo jednostavan algoritam za sortiranje, ali ima prosječnu složenost vremena slučaja od O(n2) kada se sortira lista sa n elemenata. Zbog toga sortiranje oblačićima nije pogodno za sortiranje lista sa velikim brojem elemenata. Ali zbog svoje jednostavnosti, mehurasto sortiranje se uči tokom uvoda u algoritme.
Šta je sortiranje odabirom?
Selektivno sortiranje je također još jedan algoritam za sortiranje koji počinje pronalaženjem minimalnog elementa na listi i zamjenom sa prvim elementom. Tada se minimalni element pronalazi iz ostatka liste (od drugog do posljednjeg elementa na listi) i zamjenjuje se drugim elementom. Ovaj proces se ponavlja za ostatak liste postavljanjem zamijenjenih elemenata po redu. Dakle, u sortiranju odabirom, u bilo kojem koraku algoritma, lista se dijeli na dva dijela gdje jedan dio sadrži sortirane elemente, a drugi dio sadrži nesortirane elemente. Kako algoritam napreduje, sortirana lista raste s lijeva na desno. Sortiranje odabirom također ima prosječnu složenost vremena slučaja od O(n2). Stoga također nije pogodan za sortiranje velikih lista.
Koja je razlika između mjehurića i odabira?
Iako i algoritmi sortiranja oblačićima i algoritma sortiranja odabirom imaju prosječnu složenost vremena slučaja od O(n2), sortiranje oblačićima je gotovo cijelo vrijeme bolje od sortiranja selekcijom. To je zbog broja zamjena potrebnih za dva algoritma (za sortiranje mehurića potrebno je više zamjene). Ali zbog jednostavnosti sortiranja mjehurićima, veličina njegovog koda je vrlo mala. Stabilnost je još jedna razlika u ova dva algoritma. Stabilni algoritam za sortiranje je algoritam za sortiranje koji zadržava redoslijed zapisa ako lista sadrži elemente jednake vrijednosti. U tom smislu, sortiranje selekcijom nije stabilan algoritam, dok je sortiranje mehurićem stabilan algoritam.
