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?

uzmemo drugi elemenat niza i ako je manji od prvog, zamenimo im mesta
uzmemo treći elemenat niza i ako je manji od drugog, zamenimo im mesta, zatim proverimo da li je manji i od prvog, pa ako jeste, zamenimo mesta i sa njim
uzmemo četvrti elemenat niza, pa ga uporedimo sa trećim - ako je manji, zamenimo im mesta, zatim ga uporedimo sa drugim, pa ako je manji i sa njim zameni mesto, pa ga onda uporedimo i sa prvim, pa ako je manji i sa njim zameni mesto

očigledno, na ovaj način svi prethodni elementi postaju sortirani, i svaki sledeći upoređujemo i zamenjujemo sve dok je manji... tako bi neko opšte pravilo za Insertion sort bilo:
uzmemo i-ti elemenat niza i "vučemo" ga prema početku sve dok ga ne dovedemo na odgovarajuću poziciju

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");}}
  
  Glavni ciklus kreće od drugog i ide do poslednjeg elementa. To je elemenat niza koji se ubacuje.
  Brojač j služi za uslovni ciklus. Najpre počinje od pozicije [i] elementa sa kojim radimo. 
    Inače, j služi da "pratimo" taj element kako ga "spuštamo" kroz niz.
  Uslovni ciklus se izvršava sve dok treba spuštati elemenat kroz poziciju j što proverava funkcija radi().
  Ako smo unutar ciklusa, znači da element koji je na j-toj poziciji treba "spustiti" za poziciju niže, pa tako radimo
    njegovu zamenu sa j-1 elementom.
  Pošto smo mu promenili poziciju, moramo da smanjimo j - to je sada njegova nova pozicija.
  Funkcija radi() vrši proveru da li j-ti element treba i dalje spuštati kroz niz.
  Prvo proveravamo da nije stigao do početka niza, tj. sve dok je j veće od 1...
  ...i dok je j-ti element manji od prethodnog...
  ...treba "spustiti" j-ti element, pa zato nastavljamo while ciklus.
  ...u suprotnom, znači da smo "dovukli" i-ti element na dobru poziciju 
    (bilo da je to pozicija j, bilo da je to početak niza), pa se while ciklus prekida.

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

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.