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

1 бајт уклоњен ,  пре 8 година
нема резимеа измене
(Нова страница: '''Introsort''' ili '''introspektivno sortiranje''' predstavlja algoritam sortiranja koji je dizajnirao David Musser 1997. godine. Počinje sa kviksortom i prelazi …)
 
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. 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čćajusluč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 o dubini rekurzije posle koje se prelazi na hipsort, median-of-3 tehnikom za izbor pivota i Sedgewick-ov insertion sort.
 
63

измене