WEBnSTUDY.com
Algoritmi

Sortiranje niza - Quicksort algoritam

U ovom tekstu ćemo dati objašnjenje Quicksort algoritma. Istina je da je ovaj algoritam u različitim oblicima i dan-danas ostao najbolji i najkorišćeniji algoritam sortiranja opšte namene.

Kako ovaj algoritam funkcioniše? Suštinska ideja je jednostavna:

Delovi ne moraju biti jednaki (u stvari, skoro nikada nisu jednaki) i tek da razjasnimo - elementi u njima nisu sortirani. Kako dolazimo do sortiranog niza? Stalnom deobom na sve manje i manje delove, držeći se istog jednostavnog pravila - elementi u prvom delu moraju biti manji od elemenata u drugom delu. Naravno, jasno Vam je da se to pravilo "obrće" ako želimo niz sortiran od najvećeg ka najmanjem elementu.

Deljenje niza na dva podniza kod Quicksort algoritma
Ova slika sama po sebi predstavlja suštinu Quicksort algoritma. Zavisno od vrednosti pivota, niz se deli na dva dela - u prvom delu su svi elementi manji od elemenata iz drugog dela niza. Zatim se svaki od ovih delova na isti način deli na dva podniza sve dok na kraju ne dobijemo sortiran niz.

Dakle ovo je osnova - svaki algoritam koji na ovaj način sortira elemente je Quicksort algoritam. Međutim, postoje različite varijante ovog algoritma, koje proizilaze iz glavnog problema, a to je kako efikasno podeliti niz na dva dela tako da prvi podniz sadrži manje, a drugi veće elemente?

U stvari, ovaj zadatak uopšte nije trivijalan i predstavlja pravo "srce" algoritma. Deo toliko važan da su se oko njega lomila programerska koplja tokom mnogih godina. Zaista, od načina kako se deli niz, zavisiće i brzina algoritma u nekim specifičnim situacijama.

Ovaj deo algoritma se svodi na dva zadatka:

Idealno bi bilo kada bi delovi na koje se deli niz bili približno jednaki po broju elemenata, i kada ne bismo morali da vršimo veliki broj razmena. Quicksort je osetljiv na početno stanje elemenata niza, tj. najbolje se ponaša kada su elementi uniformno slučajno raspoređeni.

Ako pivot nije dobro izabran, postoji opasnost da dođe do najgoreg slučaja za Quicksort. To je situacija kada je početni niz već sortiran (ili skoro sortiran), ili kada su elementi jednaki (ili ima puno jednakih elemenata). Tada se dešava da se podnizovi nikako ne mogu "lepo" podeliti, već stalno dobijamo deo koji se sastoji od jednog elementa i deo koji sadrži sve ostale. U toj situaciji, čak i ovaj algoritam može biti jako usporen.

Zbog toga je izbor pivot vrednosti centralni problem ovog algoritma. Koju vrednost uzeti? Prvu? Poslednju? Iz sredine? Neku po slučajnom izboru? Ako je niz zaista slučajno poređan, nije mnogo ni bitno. Ali ako je sortiran, bolje ćemo proći sa nekom "srednjom" vrednošću.

Jedan od najčešće citiranih načina za određivanje pivot vrednosti je srednja od tri vrednosti (median of three), gde se proveravaju prvi, poslednji i srednji elemenat podniza i bira onaj koji je po vrednosti između druga dva (takođe je moguće koristiti i srednji od tri slučajno izabrana elementa).

Quicksort je moguće dodatno optimizovati, tako što bi se za delove male veličine umesto "dubljeg" ulaženja u rekurziju, koristio neki drugi metod sortiranja (najčešće Insertion sort). U praksi se pokazalo da su ti delovi "male veličine" u stvari podnizovi od 5 do 15 elemenata (zavisi od sistema na kome se program izvršava).

Quicksort algoritam

Ovde je predstavljen originalni Hoareov metod za raspoređivanje elemenata u odnosu na pivot.

Prema njegovom algoritmu, niz "napadamo" sa leve i desne strane, tokom čega se ignorišu svi članovi niza koji i treba da budu u levom odnosno desnom delu. Kada sa leve strane stignemo do elementa koji je veći od pivota, i sa desne do nekog koji je manji, vršimo njihovu razmenu. Onda se provera nastavlja, i tako sve dok se ne "sudarimo" negde pri sredini niza.

Tako smo dobili levi deo sa manjim i desni sa većim elementima u odnosu na pivot.

a = array(200); n = 200; for (i = 1..n) { a[i] = trunc(rand()*1000); } write("Elementi niza:"); ispisNiza(a,1,n); quick(a, 1,n); function quick(niz, start, end) { if (end-start == 1) { if (niz[start]>niz[end]) { zameni(niz,start,end);} } else { x = niz[(start+end)div 2]; i = start; j = end; do { while(niz[i]<x) {i++;} while(niz[j]>x) {j--;} if (i<=j) {zameni(niz,i,j); i++; j--;} } while(i <= j); if (j > start) { quick(niz, start, j); } if (i < end) { quick(niz, i, end); } } } write(" "); write("Sortiran niz:"); ispisNiza(a,1,n); provera(a,n); function zameni(a,i,j) { t = a[i]; a[i] = a[j]; a[j] = t;} function ispisNiza(a,p,n) { t = ""; for (i = p..n) { t += a[i] + " ";} write(t); } function provera(a,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");}}

Pogledajmo i grafičku ilustraciju...

Grafički primer

Grafički primer se, zbog stalnog iscrtavanja, izvršava sporije, ali čak i tako je njegova brzina očigledno veća u odnosu na ostale opisane algoritme.

global {n,s,vis;} a = array(60); n = 50; for (i = 1..n) { a[i] = trunc(rand()*_HEIGHT/2)+10; } color("#000"); vis = _HEIGHT - _HEIGHT / 4; s = _WIDTH / n; crtaj(a,n); quick(a, 1,n); function quick(niz, start, end) { if (end-start == 1) { if (niz[start]>niz[end]) { zameni(niz,start,end); crtaj(niz,n);} } else { x = niz[(start+end)div 2]; i = start; j = end; do { while(niz[i]<x) {i++; poredi(niz,i,j);} while(niz[j]>x) {j--; poredi(niz,i,j);} if (i<=j) {zameni(niz,i,j); i++; j--; crtaj(niz,n);} } while(i <= j); if (start < j) { quick(niz, start, j); } if (end > i) { quick(niz, i, end); } } } function zameni(a,i,j) { t = a[i]; a[i] = a[j]; a[j] = t;} function poredi(a,i,j) { 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(a,n) { 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.