0

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[]?

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. ;-)

5
  • I take your point about being able to search lists of undetermined values, but for the pset we know that all integers in the list will be positive and not exceeding 65535.
    – Scott J.
    Aug 12 '17 at 7:37
  • Printing out the first 20 values of counting[] yields as expected; 0 because no values from 1-20 were found in the values[].
    – Scott J.
    Aug 12 '17 at 7:45
  • The problem is at the upper ends of the counting array where I'm getting long integers, as in the second screen shot of the code. Pset is supposed to use a linear sorting method, and the advice given is to use counting sort. Obviously I've not implemented counting sort correctly, but I'm still not clear on where these large values that show up on the upper end are coming from.
    – Scott J.
    Aug 12 '17 at 7:46
  • Interesting. OK, my suggestion to print the first 20 elements to demonstrate the issue was in error. As you said, the problem is at the top end of the array. However, the problem is still the same - the array hasn't been initialized. I ran the code and recreated the problem. When I then added code to initialize every element in the array to 0, the problem was resolved. You could add a for loop with an if statement to print array elements greater than 0 to diagnose.
    – Cliff B
    Aug 12 '17 at 16:00
  • Cliff - Many thanks for the help. That was a successful debug for me as well. Cheers!
    – Scott J.
    Aug 14 '17 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .