SORTAREA PRIN NUMĂRARE
Metoda sortării prin numărare constă în găsirea pentru fiecare element A[i], a numărului de elemente din vector, mai mici ca el. Numerele obţinute sunt memorate într-un vector C; elementele vectorului de sortat A, sunt iniţial atribuite vectorului B. Pe baza vectorului C, elementele lui B vor fi aranjate în vectorul A.
Exemplu
Vrem să sortăm urmatorul şir:
A= (9, -5, 2, 12, 4)
Elementele lui A le atribuim lui B:
B= (9, -5, 2, 12, 4)
Pentru fiecare element A[j] numărăm câte elemente sunt mai mici ca el, aceste numere reţinându-le în vectorul C:
C=(3, 0, 1, 4, 2) se reconstitue vect A astfel: A[c[1]+1]=B[1];A[c[2]+1]=B[2]...
obţinându-se vectorul A sortat (-5, 2, 4, 9, 12)
Algoritm descris în pseudocod
Pentru i ← 1,n execută
b[i] ← a[i];
sfpentru
pentru j ← 2,n execută
pentru i← 1,j-1 execută
dacă a[i]<a[j] atunci
c[j] ← c[j]+1
altfel c[i] ← c[i]+1;
sfdacă
sfpentru
sfpentru
pentru i ← 1,n execută
a[c[i]+1] ← b[i]
sfpentru
Implementare C++
void sortNumărare(int a[ ],int n)
{
int i,j;
int b[100],c[100];
for(i=0;i<n;i++)
{
c[i]=0;
b[i]=a[i];
}
for(j=1;j<n;j++)
for(i=0;i<=j-1;i++)
if(a[i]<a[j])
c[j]++;
else
c[i]++;
for(i=0;i<n;i++)
a[c[i]]=b[i];
}