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:

niz podelimo na dva dela, s tim da su svi elementi u prvom delu niza manji od elemenata iz drugog dela niza
na svaki od delova primenimo prethodni korak

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:

izbor pivota - kako da odredimo vrednost na osnovu koje delimo elemente niza na "manje" i "veće"
preraspodela elemenata - kako da uz što manje zamena postignemo da elementi manji od pivota budu u prvom, a veći u drugom podnizu, kao i šta se radi sa elementima jednakim pivotu

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");}}
  
  Kada smo kreirali niz, pozivamo funkcju za zadati niz a uz zadavanje indeksa početnog i krajnjeg elementa.
  U funkciji quick niz se prebacuje u promenljivu (referencu) niz, a početni i krajnji indeks podniza su start i end.
  Mala optimizacija - ako se podniz sastoji od samo dva elementa (razlika prvog i poslednjeg je 1)...
  ...nećemo se baviti deljenjem niza, već ćemo uporediti ta dva elementa i zameniti ih ako treba.
  ...u suprotnom, počinjemo sa deljeme na dva manja podniza i to tako što prvo biramo pivot element X, u ovom slučaju
    jednostavno kao središnji element podniza.
  Radimo sa dva indeksa. Indeks i kreće od početka...
  ...a indeks j od kraja zadatog podniza.
  Započinjemo glavnu petlju kojom se indeksi i i j približavaju jedan drugom.
  Sve dok je i-ti član niza manji od pivota X...
  ...prelazimo na sledeći član niza.
  Kada smo zavšili pretragu kroz levi deo niza, pretražujemo kroz desni deo, i sve dok je j-ti element veći od pivota X...
  ...spuštamo se na prethodni član niza.
  U ovom trenutku su indeksi pozicionirani: i na elementu koji nije odgovarajući za levi deo niza i 
    j na elementu koji nije odgovarajući za desni deo niza.
    Ove elemente treba razmeniti, ali samo ako se I i dalje nalazi levo od J (tj. dok je i manje ili jednako j).
  
  Tada razmenjujemo elemente na i-toj i j-toj poziciji i prelazimo na sledeće i i j.
  Glavna petlja se vrti sve dok i i j ne "zamene mesta", odnosno j pređe levo, a i desno.
  Pošto je jsada manje od i, logično je da gledamo deo niza od start do j. 
    Samo ako je j veći od start...
  ...ulazimo u rekurziju gde funkcija quick() poziva samu sebe, ali sada za levi podniz 
    - samo elementi od start pa do j (elementi manji od pivota).
  Potpuno istom logikom, ako ima prostora između i i end...
  ...ulazimo u rekurziju za desni deo niza (tu su elementi veći od pivota).
  
  
  Bilo šta se radi samo ako je start manji od end, odnosno ako u podnizu ima više od jednog elementa.

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

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.