Přihrádkové řazení

Přihrádkové řazení (anglicky bucket sort) je stabilní řadicí algoritmus. Algoritmus rozděluje vstupní data na několik částí (přihrádek, anglicky bucketů). Tyto části jsou následně seřazeny.

Předpoklady

• Algoritmus je vhodný pro rovnoměrně rozložené hodnoty vstupních dat.
• Algoritmus řazení použitý pro seřazení přihrádek musí být stabilní. Pokud stabilním není, tak ani výsledný bucket sort neřadí stabilně.

Princip

• V prvním kroku jsou vstupní data rozdělena do předem definovaného počtu přihrádek.
• V druhém kroku je na každou přihrádku volán stabilní řadicí algoritmus.
• V třetím kroku jsou jednotlivé přihrádky postupně kopírovány do výstupního pole.

Složitost

Asymptotická složitost algoritmu je ${\displaystyle O(n*k)}$, kde ${\displaystyle k=n/m}$. Vstupní data mají velikost ${\displaystyle n}$. Počet přihrádek je ${\displaystyle m}$.

Výhody

Bucket sort lze využít pro distribuované řazení. Každá přihrádka může být řazena v jiném vlákně.

Algoritmus lze použít pro řazení vstupních množin které nelze najednou načíst do paměti. Jednotlivé přihrádky mohou být řazeny ve vnitřní paměti a neaktivní přihrádky mohou být dočasně uloženy na vnější paměti.

Externí odkazy

• Obrázky, zvuky či videa k tématu přihrádkové řazení na Wikimedia Commons