Edényrendezés (algoritmus)

A Programozás Wiki wikiből
(Edény rendezés (algoritmus) szócikkből átirányítva)

Edényrendezés esetén abból indulunk ki, hogy ha sikerül az elemeket egymástól (sorrendben) elkülönülő csoportokba osztani, akkor az egyes csoportok rendezése után azok rendezett sorozattá fűzhetők össze.

Ha a bemenet például a [0,1) intervallumon egyenletes eloszlású számok sorozata, akkor ezt az intervallumot feloszthatjuk n egyenlő részre (ezek lesznek az edények).

Az edényekbe szétosztjuk az elemeket,mindegyik edényben egy listát kezelve. Az azonos edényben lévőket (pl. beszúrásos módszer szerint) rendezzük,majd a listákat a végén összefűzzük az elsővel kezdve.

Időigény: <math> O(n) </math>

A gyakorlati alkalmazást nehezíti, hogy találni kell egy módszert az edények megvalósítására. Bizonyos esetekben (számok helyett bonyolultabb elemek) nem nyilvánvaló a megfelelő "edények" előzetes meghatározása sem. Ha nem sikerül megfelelően partícionálni az elemeket, akkor a hatékonyság közelít az edényen belüli algoritmus hatékonyságához. Az alapötlet több más rendezési algoritmussal is hasonlóságot mutat, tekinthető például a gyorsrendezés, vagy a számjegyes rendezés alapjának is.