Sortiranje niza - Bubble sort algoritam

U ovom tekstu ćemo objasniti funkcionisanje Bubble sort algoritma za sortiranje nizova, koji se zasniva na principu međusobne zamene elemenata.

Da vidimo koja je ideja ovog algoritma:

Bubble sort je inače "ozloglašen" pošto se često uzima kao primer lošeg algoritma. Razmislite - da bismo sortirali N elemenata moramo imati N prolazaka, doduše kroz sve manji i manji deo niza. Suštinski prvo prolazimo kroz N-1, pa kroz N-2, onda kroz N-3 itd. elemenata, što ukupno izađe oko N2/2 upoređivanja, dok broj razmena zavisi od početnog stanja niza.

Ipak, takav kakav je, ovaj algoritam nam je interesantan zbog toga što predstavlja osnovni algoritam za sortiranje niza metodom razmene i dobar je kao referenca za upoređivanje sa drugim algoritmima.

U sledećem okviru smo dali primer Bubble sort algoritma koji možete proučiti i isprobati kako radi.

Bubble sort algoritam

Ovde imamo konkretno napravljen primer Bubble sort algoritma u pseudo-kodu, koji sortira niz od 200 slučajno izabranih elemenata.

Niz se na početku ispisuje, zatim se vrši sortiranje, pa se onda ponovo ispisuje. Na kraju se obavlja provera, da li je niz neopadajući. Koristimo pomoćne funkcije ispisNiza() i provera().

Osim toga imamo i funkciju zamena(), kojoj zadajemo indekse dva elementa koje treba zameniti. Pošto je zamena vrednosti dva elementa (promenljive) trivijalan zadatak, napravili smo ovu funkciju kako bi sam algoritam za sortiranje bio što "čistiji".

global {a;} a = array(250); n = 200; for (i = 1..n) { a[i] = trunc(rand()*1000); } write("Elementi niza:"); ispisNiza(n); for (i = 1..n) { for (j = 1..n-i) { if (a[j]>a[j+1]) { zameni(j, j+1); } } } write(" "); write("Sortiran niz:"); ispisNiza(n); provera(n); function zameni(i,j) { t = a[i]; a[i] = a[j]; a[j] = t;} function ispisNiza(n) { t = ""; for (i = 1..n) { t += a[i] + " ";} write(t); } function provera(n) {r = true; for (i = 2..n) { r = r and a[i-1]<=a[i];} if(r){write("Niz je neopadajuci");}else{write("Niz NIJE sortiran");}}

Kao što vidite, sam algoritam je efektivno veoma kratak i jednostavan.

Ako vam do sada nije nešto bilo jasno, sve će se razjasniti kada pokrenite pseudo-kod u sledećem okviru i vidite grafički prikaz.

Grafički primer

Ovde prikazujemo kako radi Bubble sort algoritam kroz animirani grafički prikaz sortiranja niza od 50 elemenata. Pošto se tokom sortiranja stalno vrši iscrtavanje koje usporava rad, ovo nije verna slika brzine sortiranja, već samo ilustrativni primer.

global { a,n,s,vis,brz,bru; } a = array(100); n = 50; for (i = 1..n) { a[i] = trunc(rand()*_HEIGHT/2) + 10; } color("#000"); vis = _HEIGHT - _HEIGHT / 4; s = _WIDTH / n; bru = 0; brz = 0; for (i = 1..n) { for (j = 1..n-i) { poredi(j, j+1); if (a[j+1]<a[j]) { zameni(j, j+1); crtaj(); } } } write(n + " elemenata"); write(bru + " upoređivanja"); write(brz + " zamena"); function zameni(i,j) { brz++; t = a[i]; a[i] = a[j]; a[j] = t; } function poredi(i,j) { bru++; fill("#ffb"); rect((i-1)*s, vis-a[i], s,a[i]); fill("#fff"); rect((j-1)*s, vis-a[j], s,a[j]); graphic(); fill("#aaa"); rect((i-1)*s, vis-a[i], s,a[i]); rect((j-1)*s, vis-a[j], s,a[j]); graphic(); } function crtaj() { cls("#444"); fill("#aaa"); for (i = 1..n) { rect((i-1)*s, vis-a[i], s,a[i]); } graphic(); }
  1. R. Sedgewick, K. Wayne (2011): Algorithms, Boston: Pearson
  2. G. Heineman, G. Pollice, S. Selkow (2010): Algorithms in a Nutshell, Sebastopol: O’Reilly Media
  3. S. Harris, J. Ross (2006): Beginning Algorithms, Indianapolis: Wiley
  4. T. Cormen, C. Leiserson, R. Rivest, C. Stein (2009): Introduction to Algorithms, Cambridge: MIT Press
  5. N. Wirth (1985): Algorithms and Data Structures, New Jersey: Prentice Hall
Svi elementi sajta Web'n'Study, osim onih za koje je navedeno da su u javnom vlasništvu, vlasništvo su autora i ne smeju se koristiti, u celosti ili delimično bez pismenog odobrenja autora. To uključuje tekstove, slike, ilustracije, animacije, prateći grafički materijal i programski kod.
Ovaj sajt koristi tehnologiju kolačića (cookies). Detaljnije o tome možete pročitati u tekstu o našoj politici privatnosti.