Introsort

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

Introsort

Namena sortiranje Struktura podataka niz Vremenska kompl.

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. ). Takvi ulazi bi potencijalno mogli biti iskorišćeni od strane agresora, na primer slanjem takve liste na server da bi se izazvao DoS (engl. ) napad.

Musser je objavio da je na 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 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.

Majkrosoftova biblioteka, počevši od verzije 4.5 koristi introsort umesto kviksorta.

Literatura

• Musser, David (1997). „Introspective Sorting and Selection Algorithms」. Software: Practice and Experience. Wiley. 27 (8): 983—993. doi:10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-#. Архивирано из оригинала 16. 07. 2012. г. Приступљено 22. 05. 2013.