1
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Avoid sizeot(TYPE) in favor of sizeof expr: Repetition is error-prone. \$\endgroup\$ – Deduplicator Jun 10 '18 at 14:31
  • \$\begingroup\$ 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. \$\endgroup\$ – Cris Luengo Jun 16 '18 at 13:36
2
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.