| Strukture podataka i algoritmi |
| Poredjenje Quick i Heap Sort-a |
Empirijske studije pokazuju da je u opstem slucaju Quick Sort znacajno brzi od Heap Sort-a.
U sledecoj tabeli su dati brojevi operacija poredjenja i zamene mesta kod tri razlicita algoritma za sortiranje na istom skupu podataka:
| n | Quick Sort | Heap Sort | Sortiranje umetanjem | |||
|---|---|---|---|---|---|---|
| Poredjenja | Zamena mesta | Poredjenja | Zamena mesta | Poredjenja | Zamena mesta | |
| 100 | 712 | 148 | 2,842 | 581 | 2,595 | 899 |
| 200 | 1,682 | 328 | 9,736 | 1,366 | 10,307 | 3,503 |
| 500 | 5,102 | 919 | 53,113 | 4,042 | 62,746 | 21,083 |
Stoga, kada mozemo da podnesemo povremenu "eksploziju" u O(n2), i dalje mozemo ocekivati da ce u proseku Quick Sort dati znacajno bolje performanse - pogotovo ako se koriste neka od modifikovanih procedura za izbor srednjeg elementa.
Vecina komercijalnih aplikacija bi koristila Quick Sort za poboljsanje prosecnih performansi: one mogu da tolerisu povremeno sporije izvrsavanje (sto otprilike znaci da ce trebati malo vise vremena za kreiranje izvestaja u danima punog meseca u prestupnim godinama) u zamenu za brze izvrsavanje u vecini slucajeva.
Medjutim, Quick Sort ne bi trebalo nikad koristiti u aplikacijama koje garantuju vreme odziva, osim ako se ne tretira kao O(n2) algoritam prilikom racunanja vremena odziva u najgorem slucaju. Ako morate da pretpostavite O(n2) vreme, onda - ako je n malo, bolje ce biti da koristite sortiranje umetanjem - koje ima jednostavniji kod i, shodno tome, manje konstantne faktore.
A ukoliko je n veliko, tada bi ocigledno trebalo da koristite Heap Sort, jer garantuje O(nlog n) vreme. Softver kritican po zivot (medicinsko osmatranje, odrzavanje zivota u avionima i kosmickim letelicama) ili kritican po misiju (osmatranje i kontrola u industrijskim i istrazivackim postrojenjima koja rade sa opasnim materijalima, kontrola letelica, odbrana, itd) ce obicno imati i vreme odziva kao deo specifikacija sistema. U takvim sistema, nije prihvatljivo bazirati se na prosecnim performansama prilikom dizajna programa, vec se uvek mora uzeti u obzir najgori slucaj, i prema tome tretirati Quick Sort kao O(n2).
Za sada, nas najbolji algoritam za sortiranje ima O(nlog n) performanse: mozemo li da napravimo nesto bolje?
U opstem slucaju, odgovor je NE!
Medjutim, ako posedujemo dodatne informacije o objektima koje treba sortirati, tada mozda mozemo da sortiranje obavimo brze.
Pre toga, pogledacemo jos samo kako mozemo da iscedimo poslednju kap performansi iz Quick Sort-a.
|
Dalje na Poslednju kap performansi! Nazad na Sadrzaj |