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...
- najpre tražimo najmanji elemenat niza (pod uslovom da je zadato sortiranje od najmanjeg do najvećeg), tako što za minimum proglasimo prvi element i upoređujemo ga sa svima ostalima, dok ne naiđemo na manji, zatim taj manji upoređujemo sa ostatkom itd.
- tako dobijen minimalni element razmenjujemo sa prvim elementom - tako smo "sredili" prvi element niza
- dalje, tražimo najmanji elemenat, ali počev od drugog člana i sve ponovimo, da bismo tako
drugi najmanji element smestili na drugu poziciju
...na taj način sortiramo jedan po jedan elemenat, tako da bi se uopšteno Selection sort mogao opisati:
- i-ti element se dobija tako što zameni mesta sa najmanjim elementom dela niza od i-te pozicije do kraja (naravno, pod pretpostavkom da sortiramo niz od najmanjeg do najvećeg)
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();
}
- 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