3
\$\begingroup\$

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

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");
\$\endgroup\$
  • \$\begingroup\$ the OPs posted code contains several calls to exit() where there is allocated memory, without passing all allocated memory to free(). The result is memory leaks. The OS will cleanup after the program, BUT the result is very sloppy code. The code should always cleanup after it self, before exiting. \$\endgroup\$ – user3629249 Jul 20 '18 at 13:08
  • 1
    \$\begingroup\$ regarding: if (argc < 2) { fprintf(stderr, "Not enough arguments given.\n"); this does not tell the user what the arguments should be. Suggest fprintf( stderr, "USAGE: %s <int1 to sort> ... <intN to sort>\n" , argv[0] ); \$\endgroup\$ – user3629249 Jul 20 '18 at 13:12
  • \$\begingroup\$ Your suggested improvement to the error message is great - I suggest you post your own answer! As to exit() without free() - that's a judgement call: I prefer to always clean up, so I can run Valgrind without lots of false-positives, but for small programs I think it's fine to use exit() knowing that resources such as memory and file descriptors will get mopped up (more efficiently than doing it within the program). Definitely a style choice, though. \$\endgroup\$ – Toby Speight Jul 20 '18 at 13:16

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.