5.6. Leszámláló rendezés (ládarendezés)

Az előbb láttuk, hogy mind a gyorsrendezés, mind a kupacrendezés O(n ln(n)) bonyolultságú, s hogy ennél jobb módszert általános esetben nem találunk. A leszámláló rendezés viszont bizonyos esetekben lineáris bonyolultságú. Ez a viszonylagos ellentmondás azzal oldódik fel, hogy a rendezendő n elem mindegyike 1 és k között helyezkedik el. A leszámláló rendezés alapötlete az, hogy meghatározza minden egyes x bemeneti elemre azoknak az elemeknek a számát, melyek kisebbek, mint az x. Ezzel az x elemet egyből a saját pozíciójába lehet helyezni a kimeneti tömbben. A módszer bonyolultsága O(n + k), így ha k = O(n), akkor a módszer lineáris. A leszamlalo.htm állomány tartalmazza azt a programot, amely egy véletlen módon generált számsorozatra végrehajtja a leszámláló rendezést.

Procedure LESZÁMLÁLÓ-RENDEZÉS(A,B,k) 
Input: Az A és B számtömb, k maximális adat 
Eredmény: Az A tömb elemeit a B tömbbe nagyság szerint rendezi 
1 //A számláló tömb törlése 
2 for i = 1 to k do 
3    C[i] = 0; 
4 endfor 
5 //Mely kulcs pontosan hányszor fordul elő? 
6 for j = 1 to A.hossz do 
7    C[A[j]] = C[A[j]] + 1; 
8 endfor 
9 //Hány kisebb vagy egyenlő kulcsú elem van a sorozatban 
10 for i = 2 to k do 
11    C[i] = C[i] + C[i − 1]; 
12 endfor 
13 for j = A.hossz downto 1 do 
14    B[C[A[j]]] = A[j]; 
15    C[A[j]] = C[A[j]] − 1; 
16 endfor