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

Innen: Programozás Wiki

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).