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. – ArtemPetrov 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! – ArtemPetrov 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 .