Introsort - Introsort

Introsort

Třída	Algoritmus řazení
Datová struktura	Pole
Nejhorší výkon	O ( n log n )
Průměrný výkon	O ( n log n )

Introsort nebo introspektivní třídění je algoritmus hybridního řazení, který poskytuje rychlý průměrný výkon a (asymptoticky) optimální výkon v nejhorším případě. Začíná quicksortem , přepne na heapsort, když hloubka rekurze překročí úroveň založenou na ( logaritmu ) počtu prvků, které jsou tříděny, a přepne na třídění vložení, když je počet prvků pod určitou prahovou hodnotou. To kombinuje dobré části tří algoritmů s praktickým výkonem srovnatelným s quicksortem u typických datových sad a nejhorším O ( n log n ) runtime díky hromadnému řazení. Protože tři algoritmy, které používá, jsou srovnávací druhy , je to také srovnávací druh.

Introsort byla vynalezena Davidem Musser v Musser (1997) , ve kterém on také představil introselect , hybridní výběrového algoritmu založeného na najdete rychlý (varianta quicksortu), která spadá zpět k mediánu mediánové a poskytuje tak nejhorší-případ lineární složitost, což je optimální. Oba algoritmy byly zavedeny za účelem poskytnutí generických algoritmů pro standardní knihovnu C ++, která měla jak rychlý průměrný výkon, tak optimální výkon v nejhorším případě, což umožnilo zpřísnit požadavky na výkon. Introsort je na svém místě a není stabilní .

Pseudo kód

Pokud jsou k dispozici funkce implementace a rozdělení oddílů typu popsaného v článku quicksort , lze introsort stručně popsat jako

procedure sort(A : array):
    let maxdepth = ⌊log(length(A))⌋ × 2
    introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
        introsort(A[0:p-1], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

Faktor 2 v maximální hloubce je libovolný; lze jej vyladit pro praktický výkon. A [ i : j ] označuje řez pole položek i až j .

Analýza

V quicksortu je jednou z kritických operací volba pivot: prvek, kolem kterého je seznam rozdělen. Nejjednodušší algoritmus výběru pivotů je vzít první nebo poslední prvek seznamu jako pivot, což způsobuje špatné chování v případě tříděného nebo téměř tříděného vstupu. Varianta Niklause Wirtha používá k zabránění těmto výskytům prostřední prvek, u vykonstruovaných sekvencí degeneruje na O ( n ² ). Algoritmus pivotního výběru mediánu 3 vezme medián prvního, prostředního a posledního prvku seznamu; přestože to funguje dobře na mnoha vstupech ze skutečného světa, je stále možné vymyslet seznam zabijáků s průměrem 3, který způsobí dramatické zpomalení quicksortu na základě této techniky výběru pivotů.

Musser uvedl, že při zabijácké sekvenci mediánu 3 ze 100 000 prvků byla doba introsortu 1/200 doby rychlého třídění mediánu 3. Musser také zvážit vliv na cache z Sedgewick ‚s opožděným malé třídění, kde jsou malé rozsahy seřazené na konci v jednom průchodu zaváděcího druhu . Uvedl, že by to mohlo zdvojnásobit počet chyb v mezipaměti, ale že jeho výkon s oboustrannými frontami byl výrazně lepší a měl by být zachován pro knihovny šablon, částečně proto, že zisk v jiných případech z okamžitého třídění nebyl velký.

Implementace

Introsort nebo nějaká varianta se používá v řadě standardních funkcí řazení knihoven , včetně některých implementací řazení C ++ .

V červnu 2000 SGI C ++ Standard Template Library stl_algo.h realizace nestabilní druhu využívá Musser introsort přístupu s hloubkou rekurze pro přepnutí do Heapsort předán jako parametr, střední-of-3 výběr otočného a konečné vložení Knuth třídit vydávat za oddílů menších než 16.

Knihovna GNU Standard C ++ je podobná: používá introsort s maximální hloubkou 2 × log ₂ n , následovaný zařazovacím tříděním na oddílech menších než 16.

Microsoft .NET Framework Class Library , od verze 4.5 (2012), použití introsort namísto jednoduchého quicksortu.

Go používá introsort s malými úpravami: u řezů o 12 nebo méně prvcích používá Shellsort namísto vkládání a pokročilejší medián tří mediánů tří výběrů pivotů pro rychlé řazení .

Varianty

pdqsort

Quicksort (pdqsort) porazující vzory je varianta introsortu zahrnující následující vylepšení:

• Medián tří otáčení,
• Technika dělení „BlockQuicksort“ ke zmírnění sankcí za nesprávné předpovědi pobočky,
• Lineární časový výkon pro určité vstupní vzorce ( adaptivní řazení ),
• Než vyzkoušíte pomalejší heapsort, použijte ve špatných případech míchání prvků.

Rust a GAP používají pdqsort.

Reference

Všeobecné