Counting sort implemented according to pseudocode but generates segmentation fault

Question

I have implemented counting sort according to its pseudocode ( that's written on the blackboard in this video explanation ) but for some mysterious reason, it doesn't seem to work properly.

Every time I run this function, I get a segmentation fault as a result, although theoretically it should work.

My question is: I want to know why the code below will give Segmentation fault as an output.

void counting(int * array, int n){

    int *copy, *out, i,j, max, counter;

    out = (int*) malloc(sizeof(int) * n );

    max = array[0];


    // Find maximum value in main array and make a copy array of the same size
    for(i=0;i<n;++i) if(array[i] > max) max = array[i]; 
    copy = (int*) malloc(sizeof(int) * (max+1));


    // initialize copy array
    for(i=0;i<max;++i) copy[i] = 0;

    // count how often each value occurs
    for(i=0;i<n;++i) ++copy[array[i]];


    // perform cumulative sum over the array
    for(i=1;i<max;++i) copy[i] += copy[i-1];

    // sort
    for(i=n-1;i>=1;--i){
        out[copy[array[i]]] = array[i];
        --copy[array[i]];
    }

    // free memory
    free(copy);
    free(out);

    // copies end result to original array
    // for(i=0;i<n;++i) array[i] = out[i];

}

[Don't cast `malloc()`](https://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc/605858#605858). — melpomene, Sep 16 '17 at 01:09

score 0 · Answer 1 · answered Sep 16 '17 at 02:09

Both the for loops should be run till max value, not for max-1.

Following changes should help.

    for(i=0;i<=max;++i) copy[i] = 0;

    // count how often each value occurs
    for(i=0;i<n;++i) ++copy[array[i]];


    // perform cumulative sum over the array
    for(i=1;i<=max;++i) copy[i] += copy[i-1];

Hope it helps!

score 0 · Answer 2 · answered Sep 18 '17 at 00:20

The problem seems to arise from the fact that the explanation in the video assumes 1-based array indexes, while C of course uses 0-based array indexes. So a number of changes in the loops and the assignment in the out array are required:

void counting(int *array, int n){
    int *copy, *out, i, j, max, counter;

    out = malloc(sizeof(int) * n);
    max = array[0];
    for(i=1;i<n;++i) if(array[i] > max) max = array[i];  // 0 unnecessary
    copy = malloc(sizeof(int) * (max+1));
    for(i=0;i<=max;++i) copy[i] = 0;          // <=max for complete array
    for(i=0;i<n;++i) ++copy[array[i]];
    for(i=1;i<=max;++i) copy[i] += copy[i-1]; // <=max for complete array
    for(i=n-1;i>=0;--i){                      // >=0 for complete array
        out[copy[array[i]] - 1] = array[i];   // -1 because 0-based index
        --copy[array[i]];
    }
    for(i=0;i<n;++i) array[i] = out[i];
    free(copy);
    free(out);
}

With these changes the code compiles without errors and gives the correct result.

Counting sort implemented according to pseudocode but generates segmentation fault

2 Answers2