Counting sort in C, revised

Question

This is a revised follow-up to this question.

I have implemented most of the suggestions in the accepted answer. I am interested to see what I could improve in my code and what I could do to make it better.

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.

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

int max(int* arr, size_t len) {
    if (len < 1) {
        return 0;
    }
    int greatest = arr[0];
    for (size_t i = 0; i < len; i++)
        if (arr[i] > greatest)
            greatest = arr[i];
    return greatest;
}

void sort(int* inputs, int* outputs, size_t length) {
    // 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));
    if (counts == NULL) {
        fprintf(stderr, "Memory allocation error\n");
        exit(EXIT_FAILURE);
    }

    // count numbers in input array
    for (size_t i = 0; i < length; i++) {
        counts[inputs[i]]++;
    }

    size_t counter = 0; // keep track of where we are in output array

    // loop through all the counts
    for (int i = 0; i <= greatest; 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

    if (argc < 2) {
        fprintf(stderr, "Not enough arguments given.\n");
        exit(EXIT_FAILURE);
    }

    inputs = calloc(length, sizeof(int));
    outputs = calloc(length, sizeof(int));

    if (inputs == NULL || outputs == NULL) {
        fprintf(stderr, "Memory allocation error\n");
        exit(EXIT_FAILURE);
    }

    for (int i = 1; i < argc; i++) {
        inputs[i - 1] = atoi(argv[i]);  // assign arguments to array
        if (inputs [i - 1] < 0) {
            fprintf(stderr, "Integer %d out of range [0, 2^31)\n", inputs[i - 1]);
            exit(EXIT_FAILURE);
        }
    }

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

Answer 1

Enable more compiler warnings

I get

gcc-8 -std=c11 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds      -Wconversion    199801.c    -o 199801

199801.c:21:35: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
     int* counts = calloc(greatest + 1, sizeof(int));
                          ~~~~~~~~~^~~
199801.c: In function ‘main’:
199801.c:45:21: warning: conversion to ‘size_t’ {aka ‘long unsigned int’} from ‘int’ may change the sign of the result [-Wsign-conversion]
     size_t length = argc - 1;   // number of integers to sort

The second of these can simply be silenced with a cast (since we have confirmed that argc >= 2), but the first probably indicates that greatest should be an unsigned type. In fact, as we only accept positive values as input, we should probably use that same unsigned type for all the values we accept.

Match allocations and types automatically

You can help your code adapt better to changes in type (and make it easier to review), by allocating memory in terms of the pointer being assigned to:

int* counts = calloc(greatest + 1, sizeof *counts);

inputs = calloc(length, sizeof *inputs);

Now, if you decide to change type of counts is changed (perhaps to unsigned short), then it only needs to be changed in the one place, and there's less risk of inconsistency. For inputs, it's now clear to reviewers that the type matches, without having to search back for the declaration (that said, in this case, it's probably better to declare it where it's initialized - we're not in C89 any more!).

Don't compare element 0 against itself

This is a trivial change, but will show understanding:

int greatest = arr[0];
for (size_t i = 0; i < len; i++)
    if (arr[i] > greatest)
        greatest = arr[i];

There's no need to compare arr[0] within the loop. So we can change the for line to:

for (size_t i = 1;  i < len;  i++)

Beware of atoi()

This function doesn't report failures very well - if its input can't be converted, it just returns 0, which is indistinguishable from atoi("0"). I recommend you look at using strtol() and family for conversion:

char *end;
long val = strtol(argv[i], &end, 10);
if (val < 0 || val > INT_MAX || !argv[i][0] || !*end) {
    fprintf(stderr, "Failed to convert input value '%s'\n", argv[i]);
    return EXIT_FAILURE;
}
inputs[i - 1] = val;

Note that my error message doesn't make assumptions about the value of INT_MAX as yours does.

Use malloc() when memory doesn't need to be cleared.

I know you've been advised to use only one of malloc() and calloc() in your program, but I disagree. Use calloc() when you want the extra behaviour of clearing the contents (or where the product of the two arguments might overflow a size_t), and use malloc() for allocations where you will be writing to the memory yourself.

Use puts() in preference to printf()

We can avoid the complexity of printf() when we output a simple newline-terminated string:

/*printf("\n");*/
puts("");    /* simpler */

Similarly:

    fputs(stderr, "Memory allocation error");