Introsort — разлика између измена

28 бајтова додато ,  пре 8 година
нема резимеа измене
 
'''Introsort''' ili '''introspektivno sortiranje''' predstavlja [[algoritam]] sortiranja koji je dizajnirao David Musser 1997. godine. Počinje sa [[[[kviksort]]]]om i prelazi na hipsort kada dubina rekurzije predje nivo koji se izračunava na osnovu ([[logaritam|logaritma]] od) broja elemenata niza koji se sortira. Kombinuje dobre stvari oba algoritma, sa složenošću najgoreg slučaja [[Велико_О|O]]''(n'' log ''n'') i performansi u praksi sličnih kviksortu[[kviksort]]u. Pošto oba algoritma koje koristi [[Алгоритми_сортирања#.D0.90.D0.BB.D0.B3.D0.BE.D1.80.D0.B8.D1.82.D0.BC.D0.B8_.D1.81.D0.BE.D1.80.D1.82.D0.B8.D1.80.D0.B0.D1.9A.D0.B0_.D0.BF.D0.BE.D1.80.D0.B5.D1.92.D0.B5.D1.9A.D0.B5.D0.BC|sortiraju poredjenjem]] onda i on predstavlja algoritam sortiranja poredjenjem
 
U kviksortu[[kviksort]]u, jedna od najvažnijih operacije je izbor pivota: element oko koga se niz deli. Najjednostavniji način je da se za pivot uzme prvi ili poslednji element niza, što dovodi do lošeg ponašanja algoritma u slučaju sortiranog ili delimočno sortiranog ulaza. U varijanti Niklaus Wirth-a koristi se srednji element kako bi se takve stvari sprečile, spuštajući efikasnost na O(n²) za iskonstruisane delove.. Postoji i tzv median-of-3 algoritam koji za pivota bira srednji element izmedju prvog, poslednjeg i srednjeg elementa niza; međutim, iako se ovo pokazalo kao dobro rešenje na mnogim ulazima u praksi, i dalje je moguće konstruisati listu koja bi drastično usporla [[kviksort]] ukoliko se upotrebljava ova tehnika za odabir pivota(tzv. ''median-of-3 killer list''). Takvi ulazi bi potencijalno mogli biti iskorišćeni od strane agresora, na primer slanjem takve liste na server da bi se izazvao [[Заштита_од_DoS_напада#-.7BDoS.7D-_.D0.BD.D0.B0.D0.BF.D0.B0.D0.B4|DoS]] (Denial of Service) napad.
 
Musser je objavio da je na ''median-of-3 killer'' nizu od 100.000 elemenata, vreme izvršavanja introsorta bilo 1/200 vremena izvršavanja ''median-of-3'' kviksorta[[kviksort]]a. Musser je uzeo u obzir i efekat na keš memoriju kod ''Sedgewick''-vog sortiranja malih nizova, gde se mali nizovi sortiraju na kraju jednim prolaskom koristeći [[Sortiranje ubacivanjem]]. On je objavio da će se broj promašaja keša duplirati ali će performanse sa dvostruko spregnutim listama biti značajno poboljšane.
 
Takodje, Musser je predstavio u najgorem slučaju ilinearni algoritam [[Сортирање_селекцијом| sortiranja selekcijom]] čije se vreme izvršavanja moglo uporediti sa Horovim algoritmom, jednostavna adaptacija [[[[kviksort]]]]a koji predstavlja najefikasniji algoritam [[Сортирање_селекцијом| sortiranja selekcijom]] danas korišćen u praksi. Ovaj algoritam se naziva ''Introselect'' algoritam.
 
U junu 2000. SGI standardna biblioteka stl_algo.h implementacija nestabilnog sortiranja koristi Musser- ov introsort pristup sa parametrom koji govori do kog nivoa dubine rekurzije se ide pre prelaska na hipsort, median-of-3 tehnikom za izbor pivota i Sedgewick-ov insertion sort.
 
[[Microsoft]]- ova .Net Framework biblioteka, počevši od verzije 4.5 koristi introsort umesto [[[[kviksort]]]]a.
 
 
63

измене