1

Ok so I made what I believe is a counting sort. I first wrote it in Java just to test it, and it works there, but when I transferred it to CS50 IDE (of course, I modified it slightly to C syntax) it gives me segmentation error. After launching debug50 I noticed that pointing my cursor at temp array shows it's filled with junk data and not 0's like I expected. So I tried initializing it thusly: int temp[65536] = { 0 }; Didn't work. I tried making it static. Same thing. Even tried explicitly setting all its values to 0 with a for loop... The line that's highlighted by debugger is right below "if (temp[i] != 0)". Any hints would be appreciated.

void sort(int values[], int n)
{
    // TODO: implement an O(n) sorting algorithm
    if (n < 1) 
    {
        printf("Array size n must be greater than 0.\n");
    }
    else
    {
        int temp[65536] = { 0 };

        for (int i = 0; i < n; i++)
        {
            temp[values[i]] += 1;
        }
        for (int i = 0, j = 0; i < 65536; i++)
        {
            if (temp[i] != 0)
            {
                values[j] = i;
                j++;
                temp[i] -= 1;
                i--;
            }
            if (j >= n)
            {
                break;
            }
        }
    //return;
    }
}
2

I used the debugger on it, and it looked perfectly fine. temp[0] to temp[65535] were initially 0.

Have you tried using debug50 on it, like ./generate 1000 50|debug50 ./find 127? Maybe the segmentation fault happens somewhere else?

Not sure whether it's a good idea, but I'd rewrite

        if (temp[i] != 0)
        {
            values[j] = i;
            j++;
            temp[i] -= 1;
            i--;
        }

to

        while (temp[i] > 0)
        {
            values[j++] = i;
            temp[i]--;
        }

as I have a certain dislike for changing loop variable i inside the loop. Should not change the result in any way.

(BTW: Are you meant to output something on n<1? Don't know the current task deskription, but having a helper function write to the console seems odd)

2
  • Huh, strange. And no, I haven't tried using it with generate function, I just passed it a small array I manually filled using the loop already provided in find.c. I should probably mention I've been working on this problem in reverse: I wrote the sorting algorithm first and have yet to start on search (I figured, you need sort for binary search to work anyway). I temporarily commented out a bunch of code that had to do with search, but now that I know algorithm works for you I'm thinking this may be the source of my problem. I'll try to write the search function and see if everything works. Mar 22 '17 at 18:15
  • Oh and yes, I also find i-- inside the loop a bit annoying. Didn't even think to write it the way you did. Will try it! Mar 22 '17 at 18:16

You must log in to answer this question.

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