Strukture podataka i algoritmi
7.3 Quick Sort (nastavak)

Quick Sort - Cinjenice!

Quick Sort je uopste najbolji poznati algoritam za sortiranje, ali ima ozbiljan nedostatak, koja mora da se razume pre nego sto se upotrebi u odredjenim primenama.

Sta se desava ako primenimo funkciju qsort sa prethodne strane na vec sortirani niz? Ovo je sasvim sigurno slucaju gde bismo ocekivali dobre performanse!

Medjutim, prvi pokusaj da se problem podeli na dva problema ce vratiti prazan donji deo - prvi objekat koji je izabran kao srednji element je ujedno i najmanji. Stoga prvi poziv jednostavno otkida jedan objekat i poziva qsort za gornji deo sa n-1 objekata! A ovo se desava sledecih n-2 puta! Svaki poziv funkcije za deljenje i dalje zahteva O(n) koraka - tako da smo generisali O(n) takvih poziva.

U najgorem slucaju, Quick Sort je O(n2) algoritam!

Mozemo li da ucinimo nesto po ovom pitanju?

Veliki broj varijacija jednostavnog Quick Sort-a ce u opstem slucaju dati bolje rezultate: umesto da se za srednji element bira prvi objekat, neke druge strategije daju bolje rezultate.

Srednji-od-3 elementa (Median-of-3 Pivot)

Na primer, varijanta sa srednjim-od-3 elementa bira tri moguca srednja elementa i koristi srednji od njih. Ako su tri moguca srednja elementa izabrana sa prvog, srednjeg i poslednjeg mesta, tada je lako videti da ce za vec sortirani niz, ovaj pristup dati optimalni rezultat: svaki deo ce biti tacno polovina (±jedan objekat) od velicine problema i trebace nam tacno ceiling(logn) rekurzivnih poziva.

Slucajni srednji element

Neke varijante qsort funkcije ce za srednji element jednostavno izabrati slucajni objekat. Ovo takodje radi fino za sortirane nizove - u proseku, ovakav srednji element ce dati dva priblizno jednaka dela i bice O(logn) poziva funkcije za deljenje.
Medjutim, kako god da izaberemo strategiju za nalazenje srednjeg elementa, moguce je naci patoloske slucajeve u kojima se problem nikada ne deli na priblizno jednake delove.

Stoga se Quick Sort mora uvek tretirati kao potencijalni O(n2) algoritam.

Zasto se onda maltretirati sa Quick Sort-om?

Heap Sort je uvek O(nlog n): zasto ne koristiti njega?

Dalje na Poredjenje Quick i Heap Sort-a
Nazad na Sadrzaj
© John Morris, 1998. Prevod sa engleskog, Dragan Stevanovic, 2002.