# Implementation of counting sort

I'm trying to learn more about counting sort and I just implemented the example given in CLRS, my question is: How can I improve this code?

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

void counting_sort(int *, int, int);
int find_max(int *, int);

int main(void)
{
int l_size;
int i;

scanf("%d", &l_size);

int *num_list = calloc(l_size, sizeof(int));

for (i = 0; i < l_size; i++)
scanf("%d", &num_list[i]);

int max = find_max(num_list, l_size);
counting_sort(num_list, l_size, max);

puts("Sorted:");
for (i = 0; i < l_size; i++)
printf("%d ", num_list[i]);

printf("\n");

return 0;

}

void counting_sort(int *num_list, int l_size, int max)
{
int i, j;

int *count_list = calloc(max + 1, sizeof(int)); // auxiliary array C
int *sorted_list = calloc(l_size, sizeof(int));

for (i = 0; i < l_size; i++)
count_list[num_list[i]]++;

for (i = 1; i < max + 1; i++)
count_list[i] += count_list[i - 1];

for (i = l_size - 1; i >= 0; i--)
{
sorted_list[count_list[num_list[i]] - 1] = num_list[i];
count_list[num_list[i]]--;
}

memcpy(num_list, sorted_list, l_size * sizeof(int));
}

int find_max(int *num_list, int l_size)
{
int i;
int max = num_list[0];

for (i = 1; i < l_size; i++)
{
if (num_list[i] > max)
max = num_list[i];
}

return max;
}

• Avoid sizeot(TYPE) in favor of sizeof expr: Repetition is error-prone. Jun 10 '18 at 14:31
• Actually you don’t need sorted_list at all, since you are just sorting ints (the indices are equal to the data members). Simply write count_list[i] times the value i in the num_list array. Jun 16 '18 at 13:36

You can avoid modifying the input parameter num_list and the memcopy by returning the sorted list pointer. All relevant changes to your code are marked with // (1) in the code below.

You also have a memory leak in counting_sort since you don't release count_list. The fix is marked // (2).

Same for the lists in main // (3)

Note : The program also seg faults when negative data is entered. You either have to guard against that, or also find the minimum data value, allocate count_list big enough and fix the indices when accessing it.

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

int* counting_sort(int *, int, int); // (1)
int find_max(int *, int);

int main(void)
{
int l_size;
int i;

scanf("%d", &l_size);

int *num_list = calloc(l_size, sizeof(int));

for (i = 0; i < l_size; i++)
scanf("%d", &num_list[i]);

int max = find_max(num_list, l_size);
int* sorted = counting_sort(num_list, l_size, max); // (1)

puts("Sorted:");
for (i = 0; i < l_size; i++)
printf("%d ", sorted[i]); // (1)

printf("\n");

free(sorted); // (3)
free(num_list); // (3)

return 0;
}

int* counting_sort(int *num_list, int l_size, int max) // (1)
{
int i, j;

int *count_list = calloc(max + 1, sizeof(int)); // auxiliary array C
int *sorted_list = calloc(l_size, sizeof(int));

for (i = 0; i < l_size; i++)
count_list[num_list[i]]++;

for (i = 1; i < max + 1; i++)
count_list[i] += count_list[i - 1];

for (i = l_size - 1; i >= 0; i--)
{
sorted_list[count_list[num_list[i]] - 1] = num_list[i];
count_list[num_list[i]]--;
}

free(count_list);  // (2)

return sorted_list;  // (1)
}

int find_max(int *num_list, int l_size)
{
int i;
int max = num_list[0];

for (i = 1; i < l_size; i++)
{
if (num_list[i] > max)
max = num_list[i];
}

return max;
}