Интросорт
Интросорт или интроспективно сортирање представља алгоритам сортирања који је дизајнирао Давид Масер 1997. године. Почиње са квиксортом и прелази на хипсорт када дубина рекурзије предје ниво који се израчунава на основу (логаритма од) броја елемената низа који се сортира. Комбинује добре ствари оба алгоритма, са сложеношћу најгорег случаја О(n log n) и перформанси у пракси сличних квиксорту. Пошто оба алгоритма које користи сортирају поредјењем онда и он представља алгоритам сортирања поредјењем
|
У квиксорту, једна од најважнијих операције је избор пивота: елемент око кога се низ дели. Најједноставнији начин је да се за пивот узме први или последњи елемент низа, што доводи до лошег понашања алгоритма у случају сортираног или делимочно сортираног улаза. У варијанти Никлаус Wиртх-а користи се средњи елемент како би се такве ствари спречиле, спуштајући ефикасност на О(н²) за исконструисане делове.. Постоји и тзв медиан-оф-3 алгоритам који за пивота бира средњи елемент измедју првог, последњег и средњег елемента низа; међутим, иако се ово показало као добро решење на многим улазима у пракси, и даље је могуће конструисати листу која би драстично успорла квиксорт уколико се употребљава ова техника за одабир пивота(тзв. median-of-3 killer list). Такви улази би потенцијално могли бити искоришћени од стране агресора, на пример слањем такве листе на сервер да би се изазвао ДоС (енгл. Denial of Service) напад.
Муссер је објавио да је на median-of-3 killer низу од 100.000 елемената, време извршавања интросорта било 1/200 времена извршавања медиан-оф-3 квиксорта. Муссер је узео у обзир и ефекат на кеш меморију код Седгеwицк-вог сортирања малих низова, где се мали низови сортирају на крају једним проласком користећи сортирање убацивањем. Он је објавио да ће се број промашаја кеша дуплирати али ће перформансе са двоструко спрегнутим листама бити значајно побољшане.
Такодје, Муссер је представио у најгорем случају илинеарни алгоритам сортирања селекцијом чије се време извршавања могло упоредити са Хоровим алгоритмом, једноставна адаптација квиксорта који представља најефикаснији алгоритам сортирања селекцијом данас коришћен у пракси. Овај алгоритам се назива Интроселецт алгоритам.
У јуну 2000. СГИ стандардна библиотека stl_algo.h имплементација нестабилног сортирања користи Масеров интросорт приступ са параметром који говори до ког нивоа дубине рекурзије се иде пре преласка на хипсорт, медиан-оф-3 техником за избор пивота и Седгеwицк-ов инсертион сорт.
Мајкрософтова .Net Framework библиотека, почевши од верзије 4.5 користи интросорт уместо квиксорта.
Литература уреди
- Муссер, Давид (1997). „Интроспецтиве Сортинг анд Селецтион Алгоритхмс”. Софтwаре: Працтице анд Еxпериенце. Wилеy. 27 (8): 983—993. дои:10.1002/(СИЦИ)1097-024X(199708)27:8<983::АИД-СПЕ117>3.0.ЦО;2-#. Архивирано из оригинала 16. 07. 2012. г. Приступљено 22. 05. 2013.
- Niklaus Wirth. "Algorithms and Data Structures". Prentice-Hall, Inc. 1985. ISBN 978-0-13-022005-9