WEBnSTUDY.com
Algoritmi

Sortiranje niza - Selection sort algoritam

Jedan od najjednostavnijih i najpoznatijih algoritama za sortiranje niza je svakako Selection sort, algoritam zasnovan na principu izbora odgovarajućeg elementa (od čega potiče i njegov naziv).

Prvo, pogledajmo način funkcionisanja ovog algoritma...

Jedna iteracija Selection sort algoritma
Evo kako to izgleda predstavljeno grafički - plavi deo niza je već sortiran, a element na kome se trenutno radi je prikazan tamno-crvenom bojom. Suštinski, traži se minimum svih nesortiranih (crvenih) elemenata (to će biti ovaj narandžasti), koji će se na kraju zameniti sa tamno-crvenim elementom.

Ovo je praktično jedini algoritam za sortiranje kod koga brzina soritanja ne zavisi od početnog stanja niza. Dakle kod Selection sorta nema "najboljeg" ili "najgoreg" slučaja kao kod ostalih algoritama. Jednostavno - računar uvek prolazi kroz sve elemente niza tražeći minimume. Suštinska prednost algoritma je u tome što uvek ima samo N-1 zamenu (ili maksimalno N-1 zamenu ako uvedemo dodatnu proveru), ali mana je što je broj upoređivanja ravan Bubble sortu.

Dosta teorije, pogledajmo praktičnu implementaciju algoritma.

Selection sort algoritam

Ovaj algoritam bi trebao da bude najlakši za razumevanje, s obzirom da smo već imali zadatke sa pronalaženjem indeksa minimuma niza. Ovde se to samo radi uzastopno sa delom niza umesto sa celim nizom, ali princip je isti.

Prikazani primer sortira niz u neopadajućem redosledu (znači od najmanjeg do najvećeg). Da bismo dobili suprotan redosled, tražili bismo maksimum umesto minimuma.

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-1) { min = i; for (j=i+1..n) { if (a[j] < a[min]) { min = j; } } zameni(i,min); } 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");}}

Kako sve to funkcioniše, možete pogledati i u grafičkom primeru.

Grafički primer

Ne zaboravite, zbog stalnog iscrtavanja, grafička reprezentacija funkcionisanja algoritma ne odslikava njegovu realnu brzinu.

global { a,n,s,vis, bru,brz; } 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; crtaj(); for (i=1..n-1) { min = i; for (j=i+1..n) { poredi(min,j); if (a[j] < a[min]) { min = j; } } zameni(i,min); 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) 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.