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];

}