Mjehurić sortiranje vs sortiranje umetanjem
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 umetanjem je takođe algoritam za sortiranje, koji radi tako što ubacuje element u ulaznu listu na ispravnu poziciju u listi koja je već sortirana. Ovaj proces se ponavlja sve dok se lista ne sortira.
Š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, sortiranje mehurića se uči tokom uvoda u algoritme.
Šta je sortiranje umetanjem?
Insertion sort je još jedan algoritam za sortiranje, koji radi umetanjem elementa iz ulazne liste na ispravnu poziciju u listi (koja je već sortirana). Ovaj proces se ponavlja sve dok se lista ne sortira. U sortiranju umetanjem, sortiranje se vrši na mjestu. Stoga, nakon i-te iteracije algoritma, prvi i+1 unosi na listi će biti sortirani, a ostatak liste će biti nesortirani. Prilikom svake iteracije, prvi element u nesortiranom dijelu liste će biti uzet i umetnut na ispravno mjesto u sortiranom dijelu liste. Razvrstavanje umetanjem ima prosječnu složenost vremena slučaja od O(n2). Zbog toga sortiranje umetanjem također nije prikladno za sortiranje velikih lista.
Koja je razlika između mjehurića i umetanja?
Iako i algoritmi sortiranja oblačićima i algoritma sortiranja umetanjem imaju prosječnu složenost vremena slučaja od O(n2), sortiranje oblačićima je gotovo cijelo vrijeme bolje od sortiranja umetanjem. 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. Takođe postoji varijanta sortiranja umetanjem nazvana sortiranje ljuske, koja ima vremensku složenost od O(n3/2), što bi omogućilo da se praktično koristi. Nadalje, sortiranje umetanjem je vrlo efikasno za sortiranje "skoro sortiranih" lista, u poređenju sa sortiranjem u oblačićima.
