Sa tastature unijeti proizvoljan niz cijelih brojeva, napraviti potprogram koji taj niz sortira bubble
sort algoritmom i ispisati nesortiran i sortiran niz.
Sortiranje mjehurom (engl.
Bubble sort
), ponekad pogrešno nazivan
sinking sort
, je jednostavan
algoritam za sortiranje koji radi tako što više puta prolazi kroz niz koji treba da bude sortiran i
upoređuje se svaki par susjednih elemenata. Elementi zamjenjuju mjesta ako su napisani
pogrešnim redom. Prolaz kroz niz se ponavlja se dok se ne izvrše sve potrebne zamjene, što
ukazuje da je niz sortiran. Algoritam je dobio ime zbog načina na koji najmanji elemenat
bubble
dolazi na početak niza. Pošto se samo porede elementi, ovo je komparativno sortiranje. Iako je
ovo jednostavan algoritam, većina drugih algoritama za sortiranje su efikasniji za velike nizove.
Unijet je sljedeći niz brojeve:
2
-4
7
8
4
7
Za sortiranje je korišten programski jezik C.
Bubble sort
ima najgoru složenost О(n
2
), gdje je n broj elemenata koji se sortiraju. Postoji mnogo
algoritama za sortiranje koji imaju znatno bolju složenost O(n log n). Čak i drugi algoritimi
složenosti О(n
2
), kao što je
insertion sort
, imaju tendenciju da imaju boje performanse od
bubble
sorta
. Dakle,
bubble sort
nije praktičan algoritam za sortiranje kada je n veliko. Zbog toga je i u
konkretnom slučaju korišteno n=6.
Jedina značajna prednost bubble sorta za razliku od drugih implementacija, čak i
quicksorta
, ali
ne insertion sorta, je sposobnost da otkrije da je sortiran niz efikasno ugrađen u algoritam.
Složenost
bubble sorta
nad već sortiranim nizovima (u najboljem slučaju) je O(n). Nasuprot
tome, većina drugih algoritama, čak i oni sa boljom prosečnom složenošću, obavljaju cijeli
proces sortiranja na setu i na taj način su složeniji. Međutim, ne samo da
insertion
sort ima ovaj
mehanizam, već i bolje radi na nizu koji je znatno sortiran (mali broj inverzija)
Slika 1. Programski kod za Bubble sort algoritam
Na osnovu koda predstavljenjog u prethodnoj slici kreiran je potprogram koji navedeni niz
brojeva soritra bubble sort algoritmom.
Postupak kodiranja se zasniva na slijdećem principu: Polazi se od početka niza, uproređuje svaki
susjedni par i mijenja njihov položaj ako nisu u pravom redoslijedu (slijedeći je manji od
prethodnog). Poslije svake iteracije, upoređuje se jedan element manje, sve dok više ne postoje
elementi koje treba upoređivati.
Pozicije elemenata u
bubble sortu
igraju veliku ulogu u određivanju složenosti. Veliki elementi
na početku niza ne predstavljaju problem jer se brzo zamene. Mali elementi pri kraju niza se
kreću na početak veoma sporo. Zbog toga se ove vrste elemenata respektivno nazivaju zečevi i
kornjače.
Učinjeni su razni napori da se eliminišu kornjače kako bi se poboljšala brzina
bubble sorta
.
Cocktail sort
je dvosmjerni bubble sort koji idi od početka do kraja, a onda se poništava i ide od
kraja do početka. On može da se pomjera kornjače prilično dobro, ali zadržava složenost O(n
2
).
