Counting sort in C

Question

EDIT: I have posted a follow-up to this question.

I have implemented counting sort in C. This program takes its input as integers from command line arguments, sorts the integers with counting sort, then outputs the sorted array.

This is my first attempt at implementing this and I would really like to see what I could do better in this code.

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
int max(int* arr, int len) {
 int out = arr[0];
 for (int i = 0; i < len; i++)
 if (arr[i] > out)
 out = arr[i];
 return out;
}
void sort(int** in, int** out, size_t length) {
 int* inputs = *in;
 int* outputs = *out;
 // this is the size of the array of counts
 int greatest = max(inputs, length); // find the greatest number in the array
 // allocate the array of counts
 int* counts = calloc(greatest + 1, sizeof(int));
 // count numbers in input array
 for (int i = 0; i < length; i++) {
 counts[inputs[i]]++;
 }
 int counter = 0; // keep track of where we are in output array
 // loop through all the counts
 for (int i = 0; i < (greatest + 1); i++) { // for every count in array
 for (int j = 0; j < counts[i]; j++) { // loop that many times
 outputs[counter++] = i; // add the integer being counted to the output array
 }
 }
 free(counts);
}
int main(int argc, char** argv) {
 int *inputs, *outputs;
 size_t length = argc - 1; // number of integers to sort
 inputs = malloc(sizeof(int) * (argc - 1));
 outputs = malloc(sizeof(int) * (argc - 1));
 for (int i = 1; i < argc; i++) {
 inputs[i - 1] = atoi(argv[i]); // assign arguments to array
 }
 sort(&inputs, &outputs, length);
 for (size_t i = 0; i < (length); i++) {
 printf("%d ", outputs[i]); // print space separated sorted numbers
 }
 printf("\n");
 free(inputs);
 free(outputs);
 return 0;
}

Answer 1

Why do you pass in and out to sort as int **? You only dereference them to get the underlying pointer. Just pass in the pointers (rather than the address of the pointers) and take the parameters as int *inputs and int *outputs.

You don't check any of your memory allocations for errors.

You do free up the memory you allocate, which is good.

You don't validate your input values at all. If one of the numbers is negative Bad Things will happen when you clobber memory outside of what you've allocated.

The test i < (greatest + 1) can be restated as i <= greatest.

If I run the program with no parameters, you run into Undefined Behavior in your max function with arr[0].

When allocating space for inputs and outputs in main, you use (argc - 1). You've already computed this and stored it in length, which you use elsewhere. You should use this length value when allocating memory for your arrays.

• anna328p: I've revised my program to take care of most of these issues, where can I post the revised version?
• Zeta: @DmitryKudriavtsev you can ask another question and link back to this topic. See codereview.meta.stackexchange.com/questions/1763/… for more information.

Answer 2

This is quite good so most of these comments are niggles / coding style. But...

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

Put #includes in sorted order. If you have a lot of them, it makes it easier to find a header or spot duplicates, and it can help avoid manual merges in a version control system

int max(int* arr, int len) {

• I'd avoid that name. I've come across more than one C implementation that provides a max macro, causing great confusion

  int out = arr[0];
  for (int i = 0; i < len; i++)
  

• That could be for (int i = 1; - the check below can never succeed for i = 0

• Please don't omit the braces. People think that the compiler takes account of indenting. It doesn't. And this frequently leads to errors in maintenance (ref the goto fail bug).

   if (arr[i] > out)
   out = arr[i];
   return out;
  }
  void sort(int** in, int** out, size_t length) {
   int* inputs = *in;
   int* outputs = *out;
  

• Why pass a pointer to a pointer then immediately dereference it

• in should be a pointer to const, as you aren't altering it. (int const *)

  // this is the size of the array of counts
  int greatest = max(inputs, length); // find the greatest number in the array
  // allocate the array of counts
  int* counts = calloc(greatest + 1, sizeof(int));
  

• unlike the other poster, I think calloc is appropriate here as you want zeroised memory and malloc is appropriate in the other places as you initialise them later.

• You should check if you actually got memory allocated here

  // count numbers in input array
  for (int i = 0; i < length; i++) {
   counts[inputs[i]]++;
  }
  int counter = 0; // keep track of where we are in output array
  // loop through all the counts
  for (int i = 0; i < (greatest + 1); i++) { // for every count in array
   for (int j = 0; j < counts[i]; j++) { // loop that many times
   outputs[counter++] = i; // add the integer being counted to the output array
  

• personally I'd avoid using auto-increments as part of an expression and make that two statements. I doubt the compiler would produce worse code, and it saves you having to work out whether the increment is done before or after the value is accessed.

   }
   }
   free(counts);
  }
  int main(int argc, char** argv) {
   int *inputs, *outputs;
   size_t length = argc - 1; // number of integers to sort
  

• declare variables as close as possible to where you use them. These next two lines should be declarations

• You don't check it the malloc was succesful

• if argc is 1, then length is 0, and you'll attempt to allocate a very large amount of memory here

  inputs = malloc(sizeof(int) * (argc - 1));
  outputs = malloc(sizeof(int) * (argc - 1));
  for (int i = 1; i < argc; i++) {
   inputs[i - 1] = atoi(argv[i]); // assign arguments to array
  }
  sort(&inputs, &outputs, length);
  for (size_t i = 0; i < (length); i++) {
   printf("%d ", outputs[i]); // print space separated sorted numbers
  }
  printf("\n");
  

• arguably printf is overkill. You could use putchar('\n') here

   free(inputs);
   free(outputs);
   return 0;
  }
  

• Well done for the last 3 lines (freeing up the memory and returning 0)! I've frequently seen one or both of those steps omitted.

• Toby Speight: It's perfectly legitimate to omit return 0; at the end of main() (but no other non-void function).
• Tom Tanner: I thought that was only C++?
• Toby Speight: Both C and C++.