Introsort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Introsort, neboli introspektivní třídění, je jedna z možných metod vnitřního třídění. Tuto metodu popsal v roce 1997 David Musser. Introsort se opírá o tzv. quicksort (rychlé třídění) a heapsort (třídění haldou) a vhodně je kombinuje. Výhodou je, že se snaží zamezit případům, kdy je složitost quicksortu úměrná O(n2), tj. když při dělící funkci dělíme v každém kroku tak, že tříděnou množinu prvků {a1,a2, ..., an} rozdělíme tak, že v jedné podmnožině bude jeden prvek, a v druhé n-1 prvků.

Použité metody třídění[editovat | editovat zdroj]

Quicksort[editovat | editovat zdroj]

Metoda quicksort, čili rychlé třídění spočívá v tom, že množinu tříděných dat rozdělíme na dvě podmnožiny, ty pak opět rozdělíme a tento krok opakujeme do té doby, než nám zbyde po jednom prvku. Jak si lze snadno domyslet, jeden prvek už představuje setříděnou množinu. Popsaný postup jak je vidět je rekurzivní, tj. procedura rozdělení volá automaticky sama sebe.. Rozdělení provedeme tak, že náhodně zvolíme prvek z množiny tříděných dat, ten nazveme pivot. Všechny ostatní prvky z množiny s ním porovnáme, a tím rozdělíme množinu a podmnožiny, kde v jedné jsou prvky menší a v druhé jsou prvky větší nežli pivot. Je zřejmé, že nejlepších výsledků dosáhneme, když jako pivot budeme volit medián množiny, tedy prvek, pro nějž platí, že rozdělí naši tříděnou množinu na podmnožiny lišící se maximálně o jeden prvek.

Heapsort[editovat | editovat zdroj]

Heapsort spočívá v ukládání prvků do haldy, jak vyplývá z názvu. Co je to tedy halda? Halda je strom (datový typ), do něhož jsou prvky vkládany tak, že v nižších úrovních stromu jsou prvky s menší hodnotou. (znaku, čísla atd...) Třídění haldou spočívá v tom, že prvky tříděné množiny vložíme do haldy, tak, že tam vložíme část prvků, a následně, poté, co jsou všechny prvky v haldě je postupně vyjímáme. Víme tedy, že prvky vyjmuté z haldy budou setříděny. Další variantou tohoto třídění může být třídění binárním vyhledávacím stromem. Tam jsou ovšem kladeny jiné podmínky pro vkládaní prvků, a výsledný algoritmus může být složitější.

Postup[editovat | editovat zdroj]

Základní myšlenka introspektivního třídění je vlastně jednoduchá. Na tříděnou posloupnost budeme používat klasický quicksort, při čemž si musíme kontrolovat, zda nenastává nejhorší případ (viz výše). V případě, že tento případ nastane, použijeme třídění haldou. Vyvstává ale otázka, jak zjistíme, že nastal nejhorší případ? Vyjdeme z toho, že hloubka rekurze je v nejhorším případě O(n) a v průměrném případě O(log2n), stejná je i spotřeba paměti. Z těchto tvrzení nám plyne, že nám stačí hlídat hloubku rekurze quicksortu, a pokud přesáhne určitou mez, označme si ji třeba M, tak na zbylé podposloupnosti použijeme třídění haldou. Poměrně je jasné, že pro M musí platit vztah M = O(log2n). Přesnější hodnota zatím není známa. Autor introsortu David R. Musser ve své knize Introspective Sorting and Selection Algorithms tvrdí, že dobrých výsledků dosáhneme i pro M = 2[log2n],kde [a] značí celou část čísla a.

Složitost tohoto algoritmu je O(n log2n), čili je stejná jako složitost průměrného quicksortu, a zároveň složitost nejhoršího případu je také O(n log2n), čili lepší než složitost nejhoršího případu quicksortu.