Sortiranje mjehurićima u odnosu na sortiranje umetanjem
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 umetanjem također je algoritam za sortiranje koji funkcionira umetanjem elementa u ulaznu listu na ispravnu poziciju u već sortiranoj listi. Ovaj se postupak primjenjuje više puta dok se popis ne sortira.
Š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 umetanjem?
Sortiranje umetanjem je još jedan algoritam za sortiranje, koji radi umetanjem elementa u ulaznu listu na ispravnu poziciju na listi (koja je već sortirana). Ovaj se postupak ponavlja iznova dok se popis ne sortira. Kod sortiranja umetanjem, sortiranje se provodi na mjestu. Stoga će nakon i-te iteracije algoritma prvih i+1 unosa na popisu biti sortirani, a ostatak popisa neće biti sortiran. U svakoj iteraciji, prvi element u nesortiranom dijelu popisa bit će uzet i umetnut na ispravno mjesto u sortiranom dijelu popisa. Sortiranje umetanjem ima prosječnu složenost slučaja od O(n2). Zbog toga sortiranje umetanjem također nije prikladno za sortiranje velikih popisa.
Koja je razlika između Bubble Sort i Insertion Sort?
Iako i algoritmi sortiranja u mjehurićima i sortiranja umetanjem imaju prosječnu složenost slučaja od O(n2), sortiranje u obliku mjehurića je gotovo uvijek bolje od sortiranja umetanjem. 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. Također postoji varijanta sortiranja umetanjem koja se naziva shell sortiranje, koja ima vremensku složenost od O(n3/2), što bi omogućilo njegovu praktičnu upotrebu. Nadalje, sortiranje umetanjem vrlo je učinkovito za sortiranje "gotovo sortiranih" popisa, u usporedbi s sortiranjem u obliku mjehurića.
