Countsort causing segment fault

Question

Im trying to implement a count sorting algorithm in C but I ran into a weird issue.

Basically with the input of

0 0 0 0 0 1 1 1 1 2 2 2 3 3 4 6 7 7 8 10 10 10 10 10 8 8 9 9 9 9

My code will cause a segment fault a cloud build but not on my actual PC rather on I cannot debug the cloud build but it works completely fine on my PC and delivers the desired output.

#include <stdio.h>
#include <string.h>
#include "introprog_countsort.h"
#include "arrayio.h"
#include <stdlib.h>

void count_sort_calculate_counts(int input_array[], int len, int count_array[]) {
    for (int i = 0; i < len; i++)
        count_array[input_array[i]]++;
}

void count_sort_write_output_array(int output_array[], int count_array[], SortDirection order) {
    int output_idx = 0;
    int max = output_array[0];
    output_array[0] = 0;
    if (order == ASCENDING) {
        for (int i = 0; i < max; i++) {
            if (count_array[i] == 0) {
            } else {
                for (int j = 0; j < count_array[i]; j++) {
                    output_array[output_idx++] = i;
                }
            }
        }
    } else {
        for (int i = max - 1; i > 0; i--) {
            if (count_array[i] == 0) {
                continue;
            } else {
                for (int j = 0; j < count_array[i]; j++)
                    output_array[output_idx++] = i;
            }
        }
    }
}

void count_sort(int input_array[], int len, int output_array[], SortDirection order) {
    for (int i = 0; i < len; i++)
        output_array[i] = 0;
    int max = 0;
    for (int i = 0; i < len; i++)
        max = input_array[i] > max ? input_array[i] : max;
    output_array[0] = max + 1; // PRO GAMER MOVE
    int count_array[max + 1];
    for (int i = 0; i < max + 1; i++)
        count_array[i] = 0;
    count_sort_calculate_counts(input_array, len, count_array);
    count_sort_write_output_array(output_array, count_array, order);
}

/* Ab hier Funktion extract_order_direction implementieren */
SortDirection extract_order_direction(char *order) {
    SortDirection direction = NOTDEFINED;
    if (strcmp(order, "desc") == 0)  direction = DESCENDING;
    if (strcmp(order, "asc") == 0)  direction = ASCENDING;
    return direction;
}

int main(int argc, char *argv[]) {
    int input_array[] = {
        0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 6,
        7, 7, 8, 10, 10, 10, 10, 10, 8, 8, 9, 9, 9, 9
    };
    int len = 30;

    printf("Unsortiertes Array:");
    print_array(input_array, len);

    int output_array[MAX_LAENGE];
    count_sort(input_array, len, output_array, ASCENDING);

    printf("Sortiertes Array:");
    print_array(output_array, len);
    return 0;
}

Here is the code I tried Apparently the issue is caused due to count_array but I have no idea how to potentially solve this

int *count_array = malloc((max + 1) * sizeof(int));

I tried to assign count_array like this but it didn't have any effect.

Answer 1

I don't see any reason to expect your count_sort() function to fail with the particular inputs provided by your main(). But an automated judge would typically run multiple inputs against that function, some of them exercising the various implicit and explicit extrema that the function is expected to accommodate. Issues with your sort function that could be triggered by other inputs include at least:

• The input array has elements of type int, which can take negative values. Using input elements directly as indexes into count_array will result in an out-of-bounds accesses when elements are negative.

• count_array is declared in count_sort() as a variable-length array (1) with dimension max + 1 (2). Not all C implementations support VLAs, and even for those that do, it would be pretty easy to provide an input that would require count_array to be too large for the stack.

• saving one argument to function count_sort_calculate_counts() by conveying the length of the counts array inside the output array (your "PRO GAMER MOVE") is obfuscatory and gains little of value. I would not expect to see such a thing from a bona fide professional programmer, and it would not pass code review with me.

• the expression max + 1 is at risk for integer overflow.

• if max is very large then your program may run much more slowly than it could do.