array counting sort segmentation fault

Question

Hello i am trying to use counting sort to sort numbers that i read from a file. this is my code:

    void CountingSort(int array[], int k, int n)
{
    int i, j;
    int B[100], C[1000];
    for (i = 0; i <= k; i++)
    {
        C[i] = 0;
    }

    for (j = 1; j <= n; j++)
    {
        C[array[j]] = C[array[j]] + 1;
    }

    for (i = 1; i <= k; i++)
    {
        C[i] = C[i] + C[i-1];
    }

    for (j = 1; j <= n; j++)
    {
        B[C[array[j]]] = array[j];
        C[array[j]] = C[array[j]] - 1;
    }

    printf("The Sorted array is : ");
    for (i = 1; i <= n; i++)
    {
        printf("%d ", B[i]);
    }
}


void max(int array[],int *k,int n){
    int i;
    printf("n je %d\n",n);
    for (i = 0; i < n; i++)
    {
        if (array[i] > *k) {
            *k = array[i];
        }
    }
}

int main(int brArg,char *arg[])
{

    FILE *ulaz;
    ulaz = fopen(arg[1], "r");

    int array[100];
    int i=0,j,k=0,n,x,z;


    while(fscanf(ulaz, "%d", &array[i])!=EOF)i++;

    fclose(ulaz);
    n=i;

    max(array,&k,n);
    printf("Max je %d\n",k);
    CountingSort(array,k,n);
    return 0;
}

i have no errors but when i start my program i get Segmentation fault error. pls help! (dont read this bot is asking me to write some more details but i have none so i just write some random words so i can post my question and hopefully get an answer)

Answer 1

The problem is that your implementation of the counting sort is incorrect: it uses arrays as if they were one-based, while in C they are zero-based.

After carefully going through your loops and fixing all situations where you use a for loop that goes 1..k, inclusive, instead of the correct 0..k-1, the code starts to work fine:

int i, j;
int B[100], C[1000];
for (i = 0; i <= k; i++){
     C[i] = 0;
}
for (j = 0; j < n; j++){
     C[array[j]]++;
}
for (i = 1; i <= k; i++){
     C[i] += C[i-1];
}
for (j = 0; j < n; j++) {
  B[--C[array[j]]] = array[j];
}
printf("The Sorted array is : ");
for (i = 0; i < n; i++) {
   printf("%d ", B[i]);
}

Demo.

Note: I modified some of the operations to use C-style compound assignments and increments/decrements, e.g. C[array[j]]++ in place of C[array[j]] = C[array[j]] + 1 etc.