Bucket sort

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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.