Implementation of counting sort

Question

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;
}

• Deduplicator: Avoid sizeot(TYPE) in favor of sizeof expr: Repetition is error-prone.
• Cris Luengo: 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.

Answer 1

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;
}