1960. godine K.A.Hoare je razvio najpoznatiju metodu za brzo razvrstavanje podataka. Danas se široko koristi u programiranju, jer ima puno pozitivnih svojstava: može se koristiti za opće slučajeve, zahtijeva malo povećanje dodatne memorije, kompatibilan je s različitim vrstama popisa i prikladan je za implementaciju. Ali postoje i nedostaci koje quicksort ima: kada se koristi u radu, dopuštene su mnoge pogreške i to je pomalo nestabilno.
Međutim, ovo je najgledanija verzija.Nakon pojave Hoareovih prvih obračuna mnogi su je počeli pomno proučavati. Stvorena je velika baza na teorijskim pitanjima pronalaženja vremena provedenog na radu, što je potkrijepljeno empirijskim podacima. Bilo je stvarnih prijedloga za poboljšanje glavnog algoritma i povećanje brzine rada.
Quicksort je vrlo čest i može bitisusreću se svugdje. Na temelju njega provodi se TList.Sort metoda koja postoji u svim verzijama (osim 1) Delphija, funkcija knjižnice vremena provedenog na izvršenje, qsort u C ++.
Osnovno načelo rada može se formulirati kao"podijeliti i vladati". Popis je podijeljen u dvije skupine i razvrstavanje se za svaki dio vrši po sebi. Slijedi da je potrebno više pažnje posvetiti procesu odvajanja, tijekom kojeg se događa slijedeće: određuje se osnovni element i cjelokupni popis se preuredi u odnosu na njega. S lijeve strane se gradi grupa kandidata čija su vrijednosti manje, s desne strane se prenose svi ostali. Ispada da se glavni element na poredanom popisu nalazi na pravom mjestu. Sljedeći korak je pozivanje rekurzivne funkcije sortiranja za obje strane elemenata u odnosu na osnovnu. Proces rada završava tek kad popis sadrži samo jedan element, to jest bit će sortiran. Dakle, da bi se ovladalo takvom programskom funkcijom kao brzo sortiranje, treba znati rad algoritama niže razine: a) izbor osnovnog elementa; b) najučinkovitije preuređivanje popisa za dobivanje dva skupa s manjim i većim vrijednostima.
Upoznajmo se s načelima prvog.Prilikom odabira osnovnog elementa, idealno je da srednji bude odabran s popisa. Zatim, kada se razbije, bit će podijeljena na dvije jednake polovice. Vrlo je teško izračunati prosječnu vrijednost na popisu, pa čak i najbrža vrsta zaobilazi ovu računicu. Ali odabir glavnog elementa s maksimalnom ili minimalnom vrijednošću također nije najbolja opcija. U slučaju takve definicije, jedan od kreiranih popisa zajamčeno je da je prazan, a drugi je prepun. Iz toga proizlazi zaključak da kao osnovni element treba odabrati onaj koji je bliži prosjeku, ali je udaljen od maksimuma i minimuma.
Nakon što ste odlučili, možeteidi na rad algoritma za particioniranje. To su takozvane unutarnje quicksort petlje. Sve je izgrađeno na dva brza indeksa: prvi će proći kroz elemente s lijeva na desno, drugi, naprotiv, s desna na lijevo. Operacija izvršenja započinje s desne strane: indeks prolazi kroz popis i uspoređuje sve vrijednosti s glavnom. Ciklus se smatra dovršenim ako se nađe element koji je manji ili je jednak osnovnom. Odnosno, vrši se usporedba i vrijednost indeksa opada. Na lijevoj strani posao je gotov kada se nađe veća ili jednaka vrijednost. I ovdje se vrijednost povećava u usporedbi.
U ovoj fazi algoritma za podjelu,koji sadrži quicksort, mogu se pojaviti dvije situacije. Prvi je da će indeks na lijevoj strani biti manji nego na desnoj. To ukazuje na grešku, to jest da su stavke na koje se ukazuje nalaze na popisu pogrešnim redoslijedom. Izlaz je promjena mjesta. Druga je situacija kada su oba stupa jednaka ili prekrižena. To ukazuje na uspješnu podjelu popisa, odnosno djelo se može smatrati dovršenim.
