Introsort

Introsort neboli introspektivní třídění  je třídicí algoritmus navržený Davidem Musseremv roce 1997. Používá rychlé třídění a přepíná na heapsort , když hloubka rekurze překročí určitou předem stanovenou úroveň (jako je logaritmus počtu setříděných prvků). Tento přístup kombinuje silné stránky obou metod s nejhorším případem O ( n log n ) a rychlostí srovnatelnou s quicksortem. Vzhledem k tomu, že oba algoritmy používají porovnávání, patří i tento algoritmus do třídy třídění založeného na porovnání .

V quicksortu je jednou z kritických operací volba podpory (prvku, podle kterého je pole rozděleno). Nejjednodušší algoritmus pro výběr základu - brát první nebo poslední prvek pole jako podporu je plné špatného chování na setříděných nebo téměř setříděných datech. Niklaus Wirth navrhl použít střední prvek, aby se zabránilo degradaci tohoto případu na O( n ²) na špatných vstupech. Algoritmus výběru mediánu tří podpory vybere jako podporu střed prvního, středního a posledního prvku pole. I když to funguje dobře na většině vstupů, stále je možné najít vstupy, které tento třídicí algoritmus hodně zpomalují. Taková data mohou být potenciálně zneužita útočníky. Útočníci mohou například odeslat takové pole na webový server , aby dosáhli odmítnutí služby .

Musser zjistil, že na nejhorším souboru dat pro medián tří algoritmů rychlého třídění (uvažovalo se pole 100 000 prvků) je introsort asi 200krát rychlejší. Posoudil také efekt vyrovnávací paměti v případě řazení Roberta Sedgwicka , kde jsou malé rozsahy seřazeny na konci jediným průchodem řazení vložením . Zjistil, že tento přístup může zdvojnásobit počet vynechání mezipaměti, ale jeho výkon je mnohem lepší při použití deque a měl by být ponechán na knihovnách šablon, částečně proto, že zisky jinak nejsou velké.

Implementace knihovny C++ Standard Template Library ( stl_algo.h ) od SGI využívá Musserův přístup řízení hloubky rekurze pro nestabilní řazení , přepíná na heapsort , volí pevný prvek jako medián tří a nakonec aplikuje Knuthův algoritmus řazení pro vkládání pro sekvence obsahující méně než 16 prvků.

Literatura

• Musser, David. Introspektivní algoritmy třídění a výběru  (anglicky)  // Software: Practice and Experience. - Wiley, 1997. - Sv. 27 , č. 8 . - str. 983-993 . - doi : 10.1002/(SICI)1097-024X(199708)27:8<983::AID-SPE117>3.0.CO;2-# .

• Niklaus Wirth. „Algoritmy a datové struktury“. Prentice-Hall, Inc., 1985. ISBN 0-13-022005-1 .

Odkazy

• "Úvod do introsortu" Článek vytvořený Ralphem Undenem jako součást studentského výzkumu. Obsahuje implementaci Java.