Introsort

Technology

12 hours ago

Author

Introsort nebo také 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. algoritmy rychlého řazení a řazení haldou a vhodně je kombinuje. Výhodou je, že se snaží zamezit případům, kdy je složitost rychlého řazení úměrná O(n2), tj. když při dělicí 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í

Rychlé řazení

Metoda rychlého řazení (quick sort) 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 zbude po jednom prvku. Jak si lze snadno domyslet, jeden prvek už představuje setříděnou množinu. +more 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.

Řazení haldou

Řazení haldou spočívá v ukládání prvků do haldy, jak vyplývá z názvu. Halda je strom (datový typ), do něhož jsou prvky vkládány tak, že v nižších úrovních stromu jsou prvky s menší hodnotou (znaku, čísla, atd. +more). 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

Základní myšlenka introspektivního třídění je vlastně jednoduchá. Na tříděnou posloupnost budeme používat klasický algoritmus rychlého řazení, při čemž si musíme kontrolovat, zda nenastává nejhorší případ (viz výše). +more 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 rychlého řazení, 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 rychlého řazení, a zároveň složitost nejhoršího případu je také O(n log2n), čili lepší než složitost nejhoršího případu rychlého řazení.