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:

Upoređujemo prvi i drugi elemenat - ako nisu poređani kako se traži, menjamo im mesta
Onda upoređujemo drugi i treći element, opet, ako nisu poređani, menjamo im mesta
...
tako nastavljamo da upoređujemo dva po dva elementa i da im menjamo mesta ako je potrebno sve dok ne doguramo do kraja
(u tom trenutku je poslednji element garantovano najveći, dok su svi ostali elementi za po malo pomereni u pravom smeru)
zatim sve to radimo ispočetka, ali ne idemo do poslednjeg već do pretposlednjeg elementa

neko opšte pravilo bi bilo:
upoređujemo dva-po-dva elementa i menjamo im mesta ako nisu raspoređeni kako se traži, sve dok ne stignemo do sortiranog dela niza, kada počinjemo postupak ispočetka

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 N²/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");}}
  
  Ovo je prosto brojač koliko puta moramo da prođemo kroz niz. Suštinski, to moramo uraditi N puta, 
    pošto je to jedina garancija da će niz biti sortiran
  Ovo je unutrašnji ciklus - u pitanju je brojač dokle se ide sa upoređivanjem parova elemenata.
    Niz nas u svakom prolasku kroz ciklus vodi kroz sve manje elemenata, zato što je sve veći deo niza sortiran.
    Na primer, za niz od 10 elemenata, u prvom prolasku idemo od 1..9 da bismo sortirali 10-ti, 
    zatim od 1..8 da bismo sortirali 9-ti, pa od 1..7 da sortiramo 8-mi i tako dalje.
    
  Ako se desilo da je j-ti element veći od sledećeg (tj. j+1 elementa)...
  ...zadajemo da se ta dva elementa zamene.

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();
  }

R. Sedgewick, K. Wayne (2011): Algorithms, Boston: Pearson
G. Heineman, G. Pollice, S. Selkow (2010): Algorithms in a Nutshell, Sebastopol: O’Reilly Media
S. Harris, J. Ross (2006): Beginning Algorithms, Indianapolis: Wiley
T. Cormen, C. Leiserson, R. Rivest, C. Stein (2009): Introduction to Algorithms, Cambridge: MIT Press
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.