WEBnSTUDY.com
Algoritmi

Sortiranje niza - Insertion sort algoritam

U ovoj lekciji ćemo dati objašnjenje Insertion sort algoritma za sortiranje nizova. Ovaj algoritam se zasniva na ubacivanju jednog po jednog elementa na "odgovarajuće" mesto unutar već sortiranog dela niza (od ovog "ubacivanja" potiče i ime algoritma).

Kako funkcioniše ovaj algoritam?

Očigledno je da algoritam zavisi od početnog stanja elemenata. Najbolji slučaj je ako su elementi već sortirani po traženom redosledu, a najgori ako su elementi sortirani u suprotnom redosledu. Tada bi svaki elemenat morao da se "vuče" (uzastopnim zamenama) do početka niza i algoritam ne bi bio bolji od Bubble sorta.

Hajde sada da se bacimo na tehnički deo i proučimo kako bismo ovaj algoritam realizovali na računaru.

Insertion sort algoritam

Ovde smo napravili primer u pseudo-kodu Insertion sort algoritma, koji možete isprobati.

Specifično, kao uslov za izvršavanje uslovnog while() ciklusa, koristimo funkciju radi(), koja proverava dva uslova. U ovoj verziji pseudo-koda, vrši se potpuna evaluacija, što znači da se za kompleksan uslov (j > 1) AND (a[j] < a[j-1]), koji bismo inače zadali u while(), uvek proveravaju oba poduslova. Dakle, čak iako je j nezadovoljavajuće (tačnije jednako 1), opet če se proveravati i drugi deo uslova u kome imamo a[j-1], odnosno nepostojeće a[0], što bi dovelo do greške.

Zato smo u funkciji radi() razdvojili ove uslove, pa se drugi proverava samo ako važi prvi.

global {a;} a = array(250); n = 200; for (i = 1..n) { a[i] = trunc(rand()*1000); } write("Elementi niza:"); ispisNiza(n); for (i=2..n) { j=i; while( radi(j) ) { zameni(j, j-1); j--; } } function radi(j) { if (j > 1) { if (a[j] < a[j-1]) { return (true); } } return (false); } 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");}}

Prelazimo na ono najzanimljivije - grafički prikaz rada algoritma.

Grafički primer

Ovde možete videti način funkcionisanja Insertion sort algoritma kroz animirani grafički prikaz sortiranja niza od 50 elemenata. Ne zaboravite, zbog stalnog iscrtavanja, ovo ne daje vernu sliku brzine algoritma, već samo prikazuje kako on funkcioniše

global { a,n,s,vis, bru, brz; } a = array(50); 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; crtaj(); for (i=2..n) { j=i; while( radi(j) ) { zameni(j, j-1); crtaj(); j--; } } function radi(j) { if (j > 1) { poredi(j,j-1); if (a[j] < a[j-1]) { return (true); } } return (false); } 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) radi vođenja interne statistike u cilju unapređenja korisničkog iskustva. Tako prikupljeni podaci su anonimni i nedostupni trećim licima. Vaša privatnost nije ugrožena ni na koji način.