Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Přihrádkové třídění

Algoritmus (Bucket sort, Radix sort, přihrádkové třídění)

Radix sort je zvláštní třídící algoritmus - jeho složitost je totiž lineární. Dosahuje to tím, že neporovnává všechny tříděné prvky (složitost problému třídění pomocí porovnávání je , takže by to jinak nebylo možné), je ho ale možné použít jen pro třídění dat podle klíče z nějaké ne příliš velké množiny - max. rozsah tříděných hodnot závisí na tom, jak velké pole si můžeme dovolit vymezit v paměti pro tento účel.

Nejjednodušší varianta (tzv. pigeonhole sort, nebo-li counting sort) opravdu počítá s klíči ze zadaného rozmezí . Pro něj si připraví cílové pole velikosti , tj. přihrádky. Do nich pak přímo podle klíče přehazuje čtené prvky (jestliže přihrádky realizujeme jako seznamy, bude třídění dokonce stabilní). Nakonec projde přihrádky od začátku do konce a co v nich najde, to vypíše (a výstup bude setříděný). Variantou counting sortu je bucket sort, kdy se do jedné přihrádky nedávají jen prvky se stejným klíčem, ale prvky s klíčem v nějakém malém rozmezí - ty pak lze setřídit rychle, protože jich zřejmě nebude mnoho, a navíc se ušetří paměť.

Protože ale klíče velikosti max. tisíců hodnot jsou většinou trochu málo, v praxi se běžně používají složitější varianty - ty zahrnují několik průchodů nahoře popsaného algoritmu, při nichž se třídí jenom podle části klíče. Ty se dělí na ty, které začínají od nejméně významné části klíče (least significant digit radix sort) a ty, které jdou od nejvýznamnější části (most significant digit). První z nich mají tu výhodu, že lze zachovat stabilitu třídění, druhá zase může třídit i podle klíčů různé délky a zastavovat se po nalezení unikátních prefixů, takže se hodí např. pro lexikografické třídění podle řetězcových klíčů.

Třídění typu least significant digit vypadá následovně:

1. Vezmi nejméně významnou část klíče (určitý počet bitů).
2. Rozděl podle této části klíče data do přihrádek, ale v nich zachovej jejich pořadí (to je nutné kvůli následnému průchodu, zároveň to dělá z tohoto algoritmu stabilní třídění).
3. Opakuj toto pro další (významnější) část klíče.

Most significant digit varianta (rekurzivní verze, je založená na bucket sortu) běhá takto:

1. Vezmi nejvýznamnější část klíče (první písmeno, například).
2. Rozděl prvky podle této části do přihrádek (takže v jedné se jich octne docela hodně)
3. Rekurzivně setřiď každou z přihrádek (začni podle další části klíče), pokud je v ní více než jeden prvek (tohle zaručí zastavení za rozlišujícím prefixem).
4. Slep přihrádky do jedné (setříděné) posloupnosti.

Popisované algoritmy většinou potřebují času k třídění, je-li (zhruba) počet přihrádek - to znamená, že sice jde o složitost lineární, ale lineární i v počtu přihrádek, což se nemusí vždy oproti konvenčnímu třídění vyplatit. Navíc jsou problémem vysoké nároky na paměť (nelze třídění provést na místě v jediném poli). Pro malou množinu hodnot klíčů (nebo u most significant digit varianty krátké odlišující prefixy) jsou ale časově efektivnější.