#include <stdio.h>
#include <stdlib.h>


int Najveci(int* niz, int d)
{
    int najveci = niz[0], i;
    for(i=0; i<d; i++)
        if(niz[i] > najveci)    
            najveci = niz[i];

    return najveci;
}

int ctsort(int *niz, int d) 
{
    int *counts, *temp;
    int i;
    
    // Alociranje memorije za sortirani niz 
    if ((temp = (int *) malloc(d * sizeof(int))) == NULL)
       return -1;
    
    // Prepisivanje datog niza u pomocni
    for(i=0; i<d; i++)
        temp[i] = niz[i];
    
    int k = Najveci(niz, d) + 1;
    
    // Alociranje memorije za brojace
    if ((counts = (int *) malloc(k * sizeof(int))) == NULL)
       return -1;
    
    // Inicijalizacija brojaca
    for (i=0; i<k; i++)
       counts[i] = 0;
    
    // Prebrojavanje koliko se puta svaki broj pojavljuje u nizu
    for (i=0; i<d; i++)
       counts[niz[i]] += 1;
    
    
    // Podesavanje brojaca na zbir svih prethodnih pojavljivanja
    for (i=1; i<k; i++)
       counts[i] = counts[i] + counts[i-1];
    
    // Postavljanje broja na odredjeno mjesto
    for (i=0; i<d; i++) 
    {
       niz[counts[temp[i]] - 1] = temp[i];
       counts[temp[i]] -= 1;
    }
    
    
    free(counts);
    free(temp);
     
    return 0;
}

int main(int argc, char *argv[])
{
    int niz[10] = {4, 1, 2, 0, 4, 8, 5, 5, 4, 8};
       
    int i;
    
    for(i=0; i<10; i++)
        printf("%d\t", niz[i]);       
    printf("\n");
    
    ctsort(niz, 10);

    for(i=0; i<10; i++)
        printf("%d\t", niz[i]);       
    printf("\n");
    
    system("PAUSE");	
    return 0;
}