Sortare prin numarare (Counting sort)

Principiul consta in determinarea numarului de elemente mai mici decat fiecare dintre elementele x date, si astfel pozitia fiecarui element in noul vector.
Avand un vector x[] de dimensiune n, cream un vector auxiliar: c[] de dimensiune k si un vector destinatie b[] de dimensiune n, ultimul reprezentand vectorul x sortat. k reprezinta valoarea maxima din vectorul x. Odata determinate numarul de elemente mai mici decat un element din x, acesta poate fi pozitionat direct pe pozitia sa in vectorul destinatie.

De exemplu, avem sirul x [] ={6, 0, 4, 7, 1, 2 }
Elementul maxim este 7, deci k=8 pozitii rezervate pentru vectorul c[], care se umplu cu 0, c [] = { 0, 0, 0, 0, 0, 0, 0, 0}
Apoi, pentru fiecare valoare a elementelor lui x, se incrementeaza valoarea de pe pozitia c[x[j]], devenind in cazul nostru c [] = {1, 1, 1, 0, 1, 0, 1, 1} (in functie de numarul de aparitii)
Apoi, in vectorul c[] se determina cate elemente sunt mai mici decat pozitia curenta, c[] = {1, 2, 3, 3, 4, 4, 5, 6}
In vectorul b[], se seteaza pentru fiecare pozitie c[x[j]-1] valoarea lui x[j], dupa care aceasta valoare se decrementeaza. b [] = { 0, 1, 2, 4, 6, 7 }

#include "stdio.h"
#include "stdlib.h"

int afla_max (int *x, int n) {

int max = x[0], i;
for(i=1; i <> max)
max=x[i];
return max;
}

int main () {

int n=7, i , j;
int *x = (int *)malloc(n*sizeof(int));
for(i=0; i < n; i++)
x[i]= rand ()%100;

int k = afla_max(x,n)+1;

int *c = (int *)malloc (k*sizeof(int));
int *b = (int *)malloc (n*sizeof(int));

for(i=0; i < k; i++)
c[i]=0;
for(j=0; j < n; j++)
c[x[j]]++;
for(i=1; i < k; i++)
c[i]+=c[i-1];
i = 0;
int prec = -1;
for(j=0; j < k; j++) {
if(c[j] != prec && c[j] > 0 )
b[i++] = j;
prec = c[j];
}

for(i=0; i < n; i++)
printf("%d ", b[i]);
return 0;
}