Radix sort

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

Radix sort (česky Číslicové třídění) je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic (často se vstupní čísla převádějí do soustavy o jiném základu, odtud tedy název). Jelikož celočíselné hodnoty mohou reprezentovat řetězce (jména, data apod.), a dokonce i vhodně formátovaná čísla s plovoucí desetinnou čárkou, radix sort není omezen pouze na řazení celých čísel.

Většina digitálních počítačů vnitřně reprezentuje všechna data jako binární čísla, nejpřirozenější je pro něj tedy řazení podle skupin bitů (tj. podle číslic o základu 8, 16, 32, 256 apod.).

V některých případech lze dosáhnout asymptotické časové složitosti až O(n) (dolní hranice). Obecně je časová složitost Radix sortu O( (z+n)*logzu), kde z je základ zvolené číselné soustavy, n počet čísel na vstupu a u je maximální rozmezí čísel na vstupu. Tedy pokud zvolíme za základ soustavy počet čísel na vstupu (z=n), dostáváme složitost O(n*lognu). Pokud je rozmezí čísel polynomiálně velké k velikosti vstupu, lze tedy dosáhnout časové složitosti O(n). Pro neomezeně velký rozsah vstupních čísel se Radixsort nehodí.

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]