CountingSort.cpp

Try counting sort in spare time when collaborating in Algorithm and Programming course.

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

const int MAX_NUMBER_RANGE = 100;

int *generateRandomNumbers(int n)
{
	srand(NULL);
	
	int *result = (int*) malloc(sizeof(int) * n);

	for (int i = 0; i < n; i++)
	{
		result[i] = (rand() % MAX_NUMBER_RANGE) + 1;
	}

	return result;
}

void printArray(int *arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}

	printf("\n");
}

int main()
{
	int n = 20;
	int *numbers = generateRandomNumbers(n);
	int *result = (int*) calloc(n, sizeof(int));
	int *counts = (int*) calloc(MAX_NUMBER_RANGE + 1, sizeof(int));
	
	for (int i = 0; i < n; i++)
	{
		int key = numbers[i];
		counts[key]++;
	}

	for (int i = 1; i <= MAX_NUMBER_RANGE; i++)
	{
		counts[i] += counts[i - 1];
	}

	for (int i = 0; i < n; i++)
	{
		int key = numbers[i];
		int position = counts[key];
		result[position - 1] = key;
		counts[key]--;
	}
	
	printf("\nResult : ");

	for (int i = 0; i < n; i++)
		printf("%d ", result[i]);

	return 0;
}