BRZO SORTIRANJE(QUICK - SORT ENGL.)

Algoritam sortiranja koji se pokazao najbržim. Sastoji se u rekurzivnom ponavljanju razdvajanja elemenata niza oko neke vrednosti koja je usvojena za "srednju". Ovaj element se naziva PIVOT i postoje različit način da se odabere. U ovo tekstu za PIVOT je odabran krajnji element podniza u tekućoj iteraciji. Ako se npr. vrši sortiranje niza u rastućem redosledu, onda se prolaskom kroz niz, s leva na desno vrši razdvajanje tako da posle završetka iteracije na levoj strani od PIVOT-a budu vrednosti koje su manje ili jednake od PIVOT-a, a na desnoj veće. Proces se ponavlja sve dok se ne ispitaju svi elementi do PIVOT-a. Na kraju se PIVOT stavlja na pravo mesto, tj. na mesto posle levo raspoređenih elemenata, onih čije su vrednosti bile manje od PIVOT-a.
Posmatrajmo npr. sledeći nesortiran niz:

VIDEO: Brzo sortiranje postupak
Brzo sortiranje. Početni niz
Slika 1: Brzo sortiranje. Početni niz
Za PIVOT-a je usvojen element na kraju niza, tj. na poziciji 9, čija je vrednost 14. Narandžastim okvirom je obeležen tekući element niza čija se vrednost poredi sa PIVOT-om. Na slici iznad se vidi stanje u drugom prolazu. Ta vrednost se poredi sa pivotom i ako je manja, vrši se zamena sa elementom uokvirenim isprekidanom crvenom linijom. Crveni okvir pokazuje u stvari prvu sledeću poziciu desno od poslednjeg zamenjenog elementa. Sa leve strane od te pozicije svi elementi moraju biti manji od PIVOTA, u ovom primeru manji od 14.
​Dakle, ukoliko je došlo do zamene tekućeg elementa(narandžasto) i elementa(crveno), pozicija za sledeću eventualnu zamenu se pomera za jedno mesto u desno. Ukoliko je tekući element niza veći od pivota nema zamene već se prelazi na ispitivanje sledećeg elementa na desno, tj narandžasti okvir se premešta. U prvom prolazu se poredio broj 25 sa 14, i s obzirom da je veči, nije bilo zamene. U drugom prolazu, koji je prikazan na prethodnoj slici, poredi se broj 13 sa PIVOT-om i s obzirom da je manji izvršiće se zamena broja  13 i 25, tj. brojeva na poziciji 0 i 1(vidi sledeću sliku)Picture
Slika 2: Brzo sortiranje(Quick-Sort). Zamena elemenata
Element 13 se posle toga nalazi na početku niza a sledeće pozicija za eventualnu zamenu je desno na poziciji br. 1. U sledećem prolazu poredi se broj 10 sa 14(PIVOT-om), a zatim i -2. Obe ove vrednosti su manje od 14 pa će se i one zameniti i naći sa leve strane od sledeće pozicije za zamenu koja se sada premešta na poziciju 3(Crveni pravougaonik na slici 3). Sledeći član niza, 16 je veći od 14 pa se samo prelazi na sledeći element na poziciji 5, vidi sliku 3:Brzo sortiranje(Quick-Sort). Premeštanje pozicije
Slika 3: Brzo sortiranje(Quick-Sort). Premeštanje pozicije
Na kraju posmatrane iteracije, kada se uporede svi elementi niza levo od PIVOT-a, PIVOT se stavlja na odgovarajuće mesto desno od svih premeštenih članova na levoj strani. Ta pozicija je ona obeležena crvenim pravougaonikom, vidi sliku 4:Brzo sortiranje(Quick-Sort). Premeštanje PIVOT-a
Slika 4: Brzo sortiranje(Quick-Sort). Premeštanje PIVOT-a
Kod koji vrši gore prikazana razdvajanja je prikazan pomoću funkcije prikazane ispod:
/*Metoda koja vrši razdvajanje elemenata niza. Niz je metodi prosleđen kao parametar a[ ].
Takođe se prosleđuju krajnja leva pozicija posmatranog niza(podniza) "l" i krajnja desna pozicija "d"*/
void deljenjeNiza(int a[ ], int l,int d)
{
int p = a[ d ];// Pivot je element na krajnjoj poziciji
int i, j;
i=l-1;
for(j=l; j<=d-1; j++)
{
if(a[j] < p)
{
if(i != j)
{
zamena(&a[i+1],&a[j]);
i++;
}
}
}
}