#include <stdlib.h>

/* Coded by Santostefano Giovanni
 * idmgiovanni@libero.it
 */

/*Counting Sort
 *Questo algoritmo permette di sortare
 *un array di n interi in un intervallo da c ad m
 *con c<=m
 *in tempo lineare [asintoticamente O(n) ]
 *Si serve di un array di appoggio per l'operazione
 *di conteggio degli elementi di m-c interi.
 *num è il numero di elementi dell'array a
 */
void CountingSort(int a[], int num, int c, int m)
{
	int *b=NULL;
	int zero=0;
	int i=0,j=0,k=0;
	
	if(c>m || !a) return;
	
	b=malloc(sizeof(int)*(m-c+1));
	for(;i<num;i++)
	{
		b[a[i]-c]++; //count the element
	}
	
	//sort the array
	for(i=0; i<(m-c+1);i++)
	{
		for(j=0;j<b[i];j++)
		{
			a[k++]=i+c;
		}
	}
	
	free(b);

}



//Client test function
int main()
{
	int i=0;
	int a[10]={-123,2,32,-15,22,105,-1,-5,2,2};
	CountingSort(a, 10, -123, 105);
	
	for(;i<10;i++)
	{
		printf("%d,",a[i]);
	}
	return 0;
}