Přihrádkové řazení

Prvky jsou rozloženy do přihrádek

Poté jsou prvky v přihrádkách seřazeny

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 $O(n*k)$, kde $k=n/m$. Vstupní data mají velikost $n$. Počet přihrádek je $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