Leszámláló rendezés (ládarendezés) (algoritmus)

A Programozás Wiki wikiből

Feltételezi,hogy az n bemeneti elem mindegyike 1 és k € Z közötti egész szám.

Minden elemnél meghatározza a nála kisebb elemek számát (így a vizsgált elem közvetlenül a saját pozíciójába kerülhet a kimeneti tömbben,kivétel ha a tömb egyforma elemeket is tartalmaz).Egy n hosszúságú A tömbbe rakjuk az elemeket,majd ezeket egy C tömb segítségével sorrendbe rendezzük a B kimeneti tömbbe.Stabil eljárás,mert az azonos értékűek sorrendje megegyezik rendezett tömbben is.

Időigény[szerkesztés]

O(k+n), de gyakorlatban akkor érdemes ezt használni, ha k=O(n), mert ekkor a futási idő : O(n).