CODEWITHSUNDEEP
carrayscounting-sort
Marko B
Marko B

Reputation: 49

array counting sort segmentation fault

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)

Upvotes: 0

Views: 653

Answers (3)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726609

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.

Upvotes: 2

VHarisop
VHarisop

Reputation: 2826

Adding to dasblinkenlight's spot-on answer:

Is your input data guaranteed to be in the range [0, 999]? If it isn't, it's obvious that segmentation faults can and will occur. Assume that the maximum value of array is 1000. C is declared as

int C[1000];

which means that C's valid indices are 0, 1, 2, ... 999. But, at some point, you will have the following:

C[array[j]] = ... /* whatever */

where array[j] > 999 so you will be attempting an out-of-bounds memory access. The solution is simple: probe array for its maximum value and use dynamic memory allocation via malloc:

/* assuming k is the maximum value */
int * C = malloc((k + 1) * sizeof(int));

Note: an alternative to this, which would also nullify the need for an initialization loop to make all elements of C equal to 0, would be to use calloc, which dynamically allocates memory set to 0.

// allocate C with elements set to 0
int * C = calloc(k + 1, sizeof(int);

Another important factor is the range of your running indices: you seem to have forgotten that arrays in C are indexed starting from 0. To traverse an array of length K, you would do:

for (i = 0; i < K; ++i)
{ 
    processArray(array[i]); 
}

instead of

for (i = 1; i <= K; ++i)
{
    processArray(array[i]);
}

Upvotes: 0

BeyelerStudios
BeyelerStudios

Reputation: 4283

The problem most likely is here

int B[100], C[1000]; // C has space for numbers up to 999
...
for (i = 1; i <= k; i++)
    C[i] = C[i] + C[i-1]; // adding up till C[k] == sum(array)
for (j = 0; j < n; j++)
    B[C[array[j]]] = array[j]; // B has space up to 99, but C[k] is sum(array)

so you're reserving space for C for a highest value of 999 but in B you're assuming that the sum of all input values is less than 100...

the resolution of your problem is to first probe the input array and get the maximum and the sum of all input values (and minimum if the range may be negative) and allocate space accordingly

edit: you probably meant j < n and not j <= n

Upvotes: 0

Related Questions