Quick Sort je veoma efikasan algoritam za sortiranje koji je izumeo C.A.R. Hoare. On se sastoji iz dve faze:

• faza deljenja i
• faza sortiranja.

Ova osobina cini Quick Sort dobrim primerom "podeli i pokori" (divide and conquer) strategije za resavanje problema. (Primer ovog pristupa ste vec videli u proceduri za binarno pretrazivanje.) U Quick Sort-u, niz objekata koji treba sortirati delimo na dva dela i tada rekurzivno pozivamo Quick Sort da sortira dva manja dela, tj. mi delimo problem na dva manja i pokoravamo ga resavajuci manje probleme. Stoga, pokoravajuci deo Quick Sort procedure izgleda ovako:

quicksort( void *a, int low, int high ) { int pivot; /* Uslov prekida! */ if ( high > low ) { pivot = partition( a, low, high ); quicksort( a, low, pivot-1 ); quicksort( a, pivot+1, high ); } }	Pocetni korak - Prvi deo
	Sortira levi deo na isti nacin

Da bi ova strategija bila efikasna, faza deljenja mora da obezbedi da su svi objekti u jednom (donjem) delu manji od svih onih u drugom (gornjem) delu.

Zbog toga se bira srednji (pivot) element i deli tako da su svi objekti u donjem delu manji od srednjeg elementa, a da su svi objekti u gornjem delu veci od srednjeg elementa. U najopstijem slucaju, ne znamo nista o objektima koji se sortiraju, tako da je bilo koji izbor za srednji element dobar - a najjednostavnije je izabrati prvi element.

Kao ilustraciju ove ideje, mozete pogledati ovu animaciju, koja pokazuje algoritam za deljenje u kojem se objekti, koje treba sortirati, kopiraju iz originalnog niza u novi: objekti manji od srednjeg elementa se smestaju sa leve strane novog niza, a objekti veci od srednjeg elementa se smestaju sa desne strane. U poslednjem koraku, srednji element se stavlja na jedino preostalo mesto u nizu.

Animacija Quick Sort algoritma Ova animacija se bazira na predlozima Jeff-a Rohl-a; napisao ju je Woi Ang.

Primetimo da animacija koristi dva niza za objekte koje treba sortirati: stoga ona zahteva O(n) dodatnog prostora za svoj rad. Medjutim, moguce je podeliti niz bez upotrebe dodatnog niza (u mestu). Sledeca strana pokazuje uobicajenu implementaciju faze deljenja koja menja pozicije elementima u istom nizu i ne koristi dodatni prostor.

Kljucni pojmovi

"Podeli i pokori" algoritmi

Algoritmi koji resavaju (pokoravaju) probleme deleci ih na manje potprobleme sve dok problemi ne postanu toliko mali da se trivijalno resavaju.

u mestu

Algoritmi za sortiranje u mestu ne zahtevaju dodatni prostor za smestanje elemenata prilikom sortiranja; oni koriste samo prostor koji objekti zauzimaju na pocetku.

Dalje na Quick Sort: Deljenje u mestu Nazad na Sadrzaj

© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.