Bubble sort

Bubble sort

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 bubbledolazi 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 О(n2), 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 О(n2), 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 cijeliproces 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