Segmentation fault for pset3 sorting

Question

Can't seem to figure out this segmentation fault and what's causing it. My sorting algo works fine for 100 generated numbers, but at some point things start to go awry. I'm adding 1 to a counter[] where the counter index is equal to the value at value[i].

void sort(int values[], int n)
{
int counter[65535];

for(int i = 0; i < n; i++)
{
    // for each value in the array, record 1 at corresponding counter[] index
    int j = values[i];
        //eprintf("j is %i, and i is %i\n", j, i);

    counter[j] += 1;
    //eprintf("j is %i, and counter[j] is %i\n", j, counter[j]);
}

This is where values are reassigned back to values[] in order:

for(int i = 0; i < n; i++)
{
    for(int j = 1; j < 65535; j++)
    {
        if (counter[j] > 0)
        {
            values[i] = j;
            eprintf("counter[%i] is %i, values[%i] is %i\n", j, counter[j], i, values[i]);
            counter[j] -= 1;

            break;
        }
    }
}


return;
}

Here's what happens when piping in 200 values:

helpers.c:87: counter[59742] is 1, values[187] is 59742
helpers.c:87: counter[60545] is 1, values[188] is 60545
helpers.c:87: counter[62311] is 1, values[189] is 62311
helpers.c:87: counter[62558] is 1, values[190] is 62558
helpers.c:87: counter[62568] is 1569645408, values[191] is 62568
helpers.c:87: counter[62568] is 1569645407, values[192] is 62568
helpers.c:87: counter[62568] is 1569645406, values[193] is 62568
helpers.c:87: counter[62568] is 1569645405, values[194] is 62568
helpers.c:87: counter[62568] is 1569645404, values[195] is 62568
helpers.c:87: counter[62568] is 1569645403, values[196] is 62568
helpers.c:87: counter[62568] is 1569645402, values[197] is 62568
helpers.c:87: counter[62568] is 1569645401, values[198] is 62568
helpers.c:87: counter[62568] is 1569645400, values[199] is 62568

This bit is particularly confusing:

helpers.c:76: counter[62681] is 32766

Why would j increment to 32766 when presented with integer 62681 from the values[]?

Answer 1

The code creates the counter array:

                int counter[65535];

but doesn't initialize it. What is in the array? Try printing out the contents of the array (or maybe the first 20 elements) to see.

As a side note, while this will work for a list of integers with values of up to 65535, it is problematic. The code should be able to handle sorting a list of any size (up to the capacity limits of the vars used.) In computing, sorting lists with millions of elements is commonplace. So is sorting lists with undetermined values, or values with a wide range. It's also common to have a list of a comparatively small number of elements, but with a very wide domain, such as 100 random numbers between 0 and 10 million. An efficient sort will handle 100 numbers easily, but are you going to step through a 10 million element array as your code does?

It is better to sort the actual list. I'll leave it to you to do the big-O analysis on it. I'd also suggest that you try to implement a sort that actually sorts the target list itself. You really need to master this skill as a programmer.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)