Page 47 - MATINF Nr. 3

Complexitatea algoritmilor de sortare 47

ˆ
Observat ,ia 5. In anumite cazuri particulare pot exista algoritmi de sortare a unui vector cu
n componente, nebazat , i pe comparat , ii de chei, a c˘aror complexitate s˘a fie mai bun˘a decˆat
Θ(n log n).
2
De exemplu, dac˘a vectorul A = (a 1 , a 2 , . . . , a n ), n ≥ 1, are toate componentele numere
∗
naturale nenule mai mici sau egale cu m, m ∈ N , adic˘a

a 1 , a 2 , . . . , a n ∈ {1, 2, . . . , m},

un algoritm eficient de sortare a vectorului A este sortarea prin num˘ararea frecvent , elor
componentelor:

• pentru fiecare valoare k, k = 1, m, num˘ar˘am cˆate elemente ale vectorului A sunt egale cu
k, adic˘a determin˘am num˘arul

f k = card{i | i = 1, n, a i = k},

numit frecvent ,a absolut˘a de aparit , ie a valorii k ˆın vectorul A;

• vectorul sortat cresc˘ator este

(1, 1, . . . , 1, 2, 2, . . . , 2, . . . , m, m, . . . , m).
| {z } | {z } | {z }
de f 1 ori de f 2 ori de f m ori

Evident, f 1 + f 2 + . . . + f m = n.

Descrierea ˆın pseudocod a algoritmului are urm˘atoarea form˘a.
SORTNUMFRECV(A, n, B) : // vectorul B = (b 1 , b 2 , . . . , b n ) va
// cont , ine elementele vectorului A = (a 1 , a 2 , . . . , a n )
// sortate cresc˘ ator
for k = 1, m do
F[k] ← 0; // F = (f 1 , f 2 , . . . , f m ) este vectorul frecvent , elor
for i = 1, n do
F[A[i]] ← F[A[i]] + 1;
i ← 0;
for k = 1, m do
for j = 1, F[k] do
i ← i + 1;
B[i] ← k;

Algoritmul SORTNUMFRECV efectueaz˘a m atribuiri de forma F[k] ← 0, n atribuiri de
forma F[A[i]] ← F[A[i]] + 1 s , i tot n atribuiri de forma B[i] ← k (iar celelalte operat , ii nu
dep˘as , esc ordinul de cres , tere al acestora), deci are complexitatea

Θ(n + m).

Astfel, dac˘a m = n sau, mai general, p · n ≤ m ≤ q · n cu p s , i q numere reale pozitive fixate
(independente de n), atunci algoritmul SORTNUMFRECV are complexitatea Θ(n), adic˘a este
un algoritm de sortare liniar!