Vecina implementacija Quick Sort-a koristi cinjenicu da se niz moze deliti u mestu koristeci dva pointera: jedan koji se pomera sa leve strane i drugi koji se pomera sa desne strane. Oni se pomeraju prema centru sve dok levi pointer ne naidje na objekat veci od srednjeg elementa (pivot) i desni pointer ne naidje na objekat manji od srednjeg elementa. Ova dva objekta tada menjaju mesta. Pointeri dalje nastavljaju sa pomeranjem ka centru dok ne dodje do "ukrstanja", kada opet dolazi do zamene mesta. Na kraju srednji element menja mesto sa objektom na koji pokazuje desni pointer i deljenje niza je zavrseno.

int partition( void *a, int low, int high ) { int left, right; void *pivot_item; /* Za srednji element se bira prvi element */ pivot_item = a[low]; pivot = left = low; right = high; while ( left < right ) { /* Uvecavaj left dok je item < pivot */ while( a[left] <= pivot_item ) left++; /* Smanjuj right dok je item > pivot */ while( a[right] > pivot_item ) right--; if ( left < right ) SWAP(a,left,right); } /* right je konacno mesto za srednji element */ a[low] = a[right]; a[right] = pivot_item; return right; }

Obratiti paznju da prethodni kod ne proverava da left ne izlazi iz granica niza. Morate sami da dodate ovu proveru, pre nego sto pocnete da premestate objekte - kako unutar petlje, tako i pre poslednjeg premestanja van petlje.

partition obezbedjuje da su svi objekti manji od srednjeg elementa ispred njega i vraca novu poziciju srednjeg elementa. Ovo odgovara nasem uslovu za deljenje problema: svi objekti u donjem delu su sigurno manji od srednjeg elementa, dok su svi objekti u gornjem delu sigurno veci od srednjeg elementa.

Primetite da smo koristili nasu ItemCmp funkciju u okviru partition funkcije. Ovo pretpostavlja da postoji eksterna deklaracija za ItemCmp i da cemo u bilo kom programu sortirati samo jedan tip objekata. U opstem slucaju ovo nije prihvatljivo, tako da formalna specifikacija za Quick Sort u Unix i ANSI C bibliotekama ukljucuje funkciju compar cija se adresa navodi u pozivu funkcije qsort. Navodeci funkciju compar, koja definise poredak objekata kada se poziva qsort, izbegavamo ovaj problem na isti nacin kao kada smo navodili funkciju ItemCmp prilikom poziva ConsCollection.

Analiza

Obicno, procedura za deljenje ce podeliti problem u dve priblizno jednaka dela. Znamo da se n objekata moze deliti po pola log₂n puta. Ovo cini Quick Sort O(nlogn) algoritmom - ekvivalentim sa Heap Sort-om.

Medjutim, u ovom razmatranju smo napravili neopravdanu pretpostavku - mozete li je prepoznati pre nego sto nastavite.

Animacija Quick Sort algoritma Ova animacija koristi deljenje niza u mestu; napisao ju je Chien Wei Tan

Posaljite komentare na adresu morris@ee.uwa.edu.au

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.

Dalje na Quick Sort (nastavak) Nazad na Sadrzaj

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