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

30 бајтова додато ,  пре 7 година
м
Бот: исправљена преусмерења; козметичке измене
м
м (Бот: исправљена преусмерења; козметичке измене)
}}
 
'''Introsort''' ili '''introspektivno sortiranje''' predstavlja [[algoritam]] sortiranja koji je dizajnirao David Maser -{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 [[kviksort]]u. Pošto oba algoritma koje koristi [[Алгоритми сортирања#Алгоритми сортирања поређењем|sortiraju poredjenjem]] onda i on predstavlja algoritam sortiranja poredjenjem
 
U [[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_нападаЗаштита од DoS напада#DoS напад|DoS]] ({{jez-eng-lat|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'' [[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 umetanjem|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 Maserov 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.
[[Majkrosoft]]ova -{.Net Framework}- biblioteka, počevši od verzije 4.5 koristi introsort umesto [[kviksort]]a.
 
== Literatura ==
* {{cite journal |
last=Musser |
* -{Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.}-
 
[[CategoryКатегорија:Алгоритми сортирања]]
 
[[Category:Алгоритми сортирања]]
1.572.075

измена