Edényrendezés (algoritmus)

A Programozás Wiki wikiből

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.