Introsort — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
мНема описа измене |
||
Ред 1:
'''Introsort''' ili '''introspektivno sortiranje''' predstavlja [[algoritam]] sortiranja koji je dizajnirao David
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_напада#
▲'''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 [[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
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 [[
▲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_напада#-.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'' [[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.
Линија 10 ⟶ 9:
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.
[[
==
* {{cite journal |
last=Musser |
Линија 26 ⟶ 24:
year=1997 |
pages=983–993}}
* -{Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.}-▼
▲* Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.
[[Категорија:Алгоритми сортирања]]
[[Категорија:Сортирање поредјењем]]
| |||