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

С Википедије, слободне енциклопедије
Садржај обрисан Садржај додат
Нема описа измене
Нема описа измене
Ред 1: Ред 1:
'''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 koji se sortiraju. Kombinuje dobre stvari oba algoritma, sa složenošću najgoreg slučaja [[Велико_О|O]]''(n'' log ''n'') i performansi u praksi sličnih kviksortu. 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
'''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 koji se sortiraju. Kombinuje dobre stvari oba algoritma, sa složenošću najgoreg slučaja [[Велико_О|O]]''(n'' log ''n'') i performansi u praksi sličnih kviksortu. 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

{{Infobox Algorithm
|class=[[Sorting algorithm]]
|image=
|caption=
|data=[[Array data structure|Array]]
|time=O(''n'' log ''n'')
|average-time=O(''n'' log ''n'')
|space=
|optimal=
}}


U kviksortu, 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.
U kviksortu, 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.

Верзија на датум 22. мај 2013. у 21:05

Introsort ili introspektivno sortiranje predstavlja algoritam sortiranja koji je dizajnirao David Musser 1997. godine. Počinje sa kviksortom i prelazi na hipsort kada dubina rekurzije predje nivo koji se izračunava na osnovu (logaritma od) broja elemenata koji se sortiraju. Kombinuje dobre stvari oba algoritma, sa složenošću najgoreg slučaja O(n log n) i performansi u praksi sličnih kviksortu. Pošto oba algoritma koje koristi sortiraju poredjenjem onda i on predstavlja algoritam sortiranja poredjenjem

Introsort
КласаSorting algorithm
Структура податакаArray
Најгора перформанцаO(n log n)
Просечна перформанцаO(n log n)

U kviksortu, 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 (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. 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 kviksorta 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.

Microsoft- ova .Net Framework biblioteka, počevši od verzije 4.5 koristi introsort umesto kviksorta.


References

  • Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1.