trjhtr

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;

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;