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)

Does you program crash if you remove the CountingSort(array,k,n); in your main function? — dmg
– dmg, Commented Jan 16, 2015 at 16:38
Adding onto that I would throw in some debug statements to help you determine where the seg fault is happening. Once you've done that it will be easier for others to help you — sedavidw
– sedavidw, Commented Jan 16, 2015 at 16:40
Build a debug version, and run in a debugger. The debugger will then stop at the location of the crash, and let you examine and (more importantly) walk up the function call stack to your code. There you can examine values of variables. At the very least you should edit your question to indicate where in your code the crash happens. You should also provide the input that causes the crash. — Some programmer dude
– Some programmer dude, Commented Jan 16, 2015 at 16:41
i dont rly know how to do the debugging thing.. i am kinda new to programming.. but i will try to do something with some DDD program and try to get some results — Marko B
– Marko B, Commented Jan 16, 2015 at 16:47

Sergey Kalinichenko · Accepted Answer · 2015-01-16 17:07:37Z

2

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.

edited Jan 16, 2015 at 17:07

answered Jan 16, 2015 at 16:54

Sergey Kalinichenko

729k85 gold badges1.2k silver badges1.6k bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Marko B Over a year ago

thank you for you help. but there is funny thingy going on now. it doesent show seg fault its sorts numbers but kinda. in my file my max number is 70. so program now does sort other numbers nicely but insted of putting 70 last it puts some random high number at start. exmpl: number 2 5 1 3 70... sorted 123124 1 2 3 5

Sergey Kalinichenko Over a year ago

@MarkoB This is because C[array[j]] needs to be decremented before the B[C[array[j]]] = array[j]; assignment. I combined the pre-decrement with the assignment, and fixed the demo.

Marko B Over a year ago

now it works perfecty! i cant thank you enough for your help! thank you so so so much!

Sergey Kalinichenko Over a year ago

@MarkoB You are welcome! If the problem is solved, please consider accepting the answer by clicking the grey check mark next to it. This would indicate to other site visitors that you are no longer actively looking for an improved solution, and earn you a brand-new badge on Stack Overflow. Good luck with your project!

BeyelerStudios · Accepted Answer · 2015-01-16 16:53:10Z

0

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

answered Jan 16, 2015 at 16:53

BeyelerStudios

4,29322 silver badges38 bronze badges

Comments

VHarisop · Accepted Answer · 2015-01-16 17:05:03Z

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]);
}

Collectives™ on Stack Overflow

array counting sort segmentation fault

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related