Quicksort

	Quicksort
Namena	sortiranje
Struktura podataka	varira
Vremenska kompl.	O(n logn) do O(n²)
Memorijska kompl.	O(logn) do O(n)
Stabilan	ne

Kviksort (engl. quicksort, qsort; od engl. quick, brz, brzo; i engl. sort, sortiranje) je poznat algoritam sortiranja koji radi na principu podeli pa vladaj, a razvio ga je Toni Hor 1960. godine.

Princip rada algoritma

Sledi opis rada algoritma koji elemente sortira u rastućem poretku. Osnovni princip rada algoritma se deli u tri sledeće celine:

Izabiranje pivot-elementa na datom intervalu
Raspored svih elemenata manjih ili jednakih ovom pivot-elementu levo od njega, a svih većih desno od njega u nizu
Rekurzivno ponavljanje ovog postupka na novonastale intervale levo i desno od ovog pivot-elementa

Opširniji opis

Algoritam na početku dobije niz i levu i desnu granicu intervala koga treba sortirati. Za ove granice mora da važi da leva ima manji indeks od desne, inače se algoritam prekida. Unutar tog intervala, algoritam izabere tzv. pivot-element, koji se obično uzima sa njegove sredine ili njene okoline. Potom, algoritam zamenjuje mesta pivot-elementa i poslednjeg elementa u nizu (iz razloga koji će biti spomenut kasnije) i sortiranje može da počne. Algoritam prolazi kroz ceo zadat interval i sve elemente koji su manji ili jednaki tom pivot-elementu slaže na prvo, drugo, treće itd. mesto u nizu. Pritom elementi koji su se zatekli na tom prvom, drugom, trećem itd. mestu zamenjuju (engl. swap) svoja mesta za mesta nađenih elemenata. Elementi koji se već nalaze na nekom od ovih mesta i ispunjavaju uslov da na njemu ostanu se ne premeštaju.

Po završetku ovog procesa, pivot-element sa kraja intervala se stavlja na kraj ovog niza, iza zadnjeg postavljenog elementa. Taj element je sad na svom mestu i neće biti više potrebe premeštati ga. Zbog ovoga je na početku i bio premešten na kraj — da se tokom razmeštanja ne bi moralo pratiti njegovo mesto u nizu te da premeštanje na kraj bude lakše. Dati interval je sad ovim pivot-elementom podeljen na dva podintervala od kojih levi sadrži sve elemente njemu manje ili jednake, a desni sve one koji su od njega veći. Algoritam se sada ponavlja za ova dva novonastala intervala.

Proces preraspoređivanja i deljenja se na daljim podintervalima ponavlja dok se ne dođe do intervala dužine jedan ili nula, u kojima je element već na početku algoritma na svom mestu.

Primer

Recimo da kviksortom treba u rastućem poretku sortirati sledeći niz:

2 5 11 8 7 9 1 15 16 4

Prvo se izabire pivot-element otprilike na polovini niza. U ovom slučaju će to biti broj 9. Sledi premeštane svih elemenata manjih ili jednakih 9 na levu stranu niza. Crvenom bojom viće označen pivot-element, a zelenom poslednji elemenat niza na koga se preslažu elementi manji ili jednaki pivot-elementu.

2 5 11 8 7 9 1 15 16 4
2 5 11 8 7 4 1 15 16 9

2 5 11 8 7 4 1 15 16 9
2 5 11 8 7 4 1 15 16 9
2 5 8 11 7 4 1 15 16 9
2 5 8 7 11 4 1 15 16 9
2 5 8 7 4 11 1 15 16 9
2 5 8 7 4 1 11 15 16 9

Ovde je prolazak kroz niz završen i pivot-element, broj 9, će zauzeti svoje konačno mesto u nizu. Ovakvi elementi će nadalje imati plavu boju.

2 5 8 7 4 1 9 15 16 11

Prema opisu algoritma, postupak se sad ponavlja na levom novonastalom podintervalu. Nadalje će neki koraci biti preskočeni kao nebitni za praćenje

2 5 8 7 4 1   15 16 11
2 5 8 1 4 7   15 16 11

2 5 1 8 4 7   15 16 11
2 5 1 4 8 7   15 16 11
2 5 1 4 7 8   15 16 11

I opet na levom novonastalom podintervalu:

2 5 1 4   8   15 16 11
2 5 4 1   8   15 16 11

Kako ovaj put nema elementa manjeg ili jednakog pivot-elementu, pivot-element će doći na prvo mesto u podintervalu, što znači da će dužina levog podintervala biti nula. Algoritam nad ovim delom se smesta završava i kako isti nema daljih podela, prelazi se na desni deo nastao prilikom poslednje podele: deo 2, 5, 4. Nadalje će i delovi prolaska kroz niz (označavanje zelenom bojom) biti preskakani.

1 2 5 4   8   15 16 11
  2 5 4   8   15 16 11
  2 4 5   8   15 16 11

  2 4     8   15 16 11
  2 4     8   15 16 11

  2       8   15 16 11
  2       8   15 16 11

          8   15 16 11
          8   15 16 11

Podsećanje: do sada je sortiran interval koji se nalazi levo od prvog pivot-elementa, devetke, i ovako sortiran se može složiti pogledom na plave elemente u gornjim listama: 1, 2, 4, 5, 7, 8 i 9 iza njega. Algoritam sad prelazi na desnu stranu tog prvog deljenja tj. desno od broja devet. Za pivot-element se opet uzima broj na sredini intervala.

              15 16 11
              15 11 16
              15 11 16

No kako su oba broja manja od njega, i ostaje na kraju intervala, gde je kao pivot-element bio premešten. Sledeći pivot-element je broj 11, koji završava na početku intervala, jer nema elemenata koji su mu jednaki ili manji od njega.

              15 11
              11 15

A preostali broj 15 se već nalazi na svom mestu (interval dužine jedan).

Ako se pogleda naviše, videće se da je ovaj interval sortiran kao 11, 15, 16. Što se sad može spojiti sa levom stranom. Ovaj niz je sortiran:

1 2 4 5 7 8 9 11 15 16