Counting Sort

Counting sort is sorting algorithm based on keys between specific range. It works by counting the number of objects having distinct key values. Then doing some arithmetic to calculate the position of each object in the output sequence.



									void CountingSort(int* data, int n, int min, int max) {
	int cLen = max - min + 1;
	int* count = (int*)malloc(sizeof(int) * cLen);
	int z = 0;

	for (int i = 0; i < cLen; i++)
		count[i] = 0;

	for (int i = 0; i < n; i++)
		count[data[i] - min]++;

	for (int i = min; i <= max; i++)
	{
		while (count[i - min]-- > 0)
		{
			data[z] = i;
			++z;
		}
	}

	free(count);
}
								


Example

									int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
CountingSort(data, 7, -58964, 78596);
								


Output

									-58964
-119
-1
0
25
8547
78596