# Segmentation fault for pset3 sorting

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;

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 is 1, values is 59742
helpers.c:87: counter is 1, values is 60545
helpers.c:87: counter is 1, values is 62311
helpers.c:87: counter is 1, values is 62558
helpers.c:87: counter is 1569645408, values is 62568
helpers.c:87: counter is 1569645407, values is 62568
helpers.c:87: counter is 1569645406, values is 62568
helpers.c:87: counter is 1569645405, values is 62568
helpers.c:87: counter is 1569645404, values is 62568
helpers.c:87: counter is 1569645403, values is 62568
helpers.c:87: counter is 1569645402, values is 62568
helpers.c:87: counter is 1569645401, values is 62568
helpers.c:87: counter is 1569645400, values is 62568
``````

This bit is particularly confusing:

``````helpers.c:76: counter is 32766
``````

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

The code creates the counter array:

``````                int counter;
``````

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

• 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. 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[]. 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. 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. Aug 12 '17 at 16:00
• Cliff - Many thanks for the help. That was a successful debug for me as well. Cheers! Aug 14 '17 at 16:10