Debugging sort code

Question

I've been trying to write code for the sort function. It's not working properly and going through gdb isn't helping. When trying to sort 5 numbers, it seemed to go fine in gdb, but still printed out unsorted when I actually executed the program for real.

My code is as follows:

void sort(int values[], int n)
{
    // Bubble sort
    int notsorted = 0;
    do
    {
        for (int i = 0, notsorted = 0; i < n - 1; i++)
        {
            if(values[i] > values[i+1])
            {
                int x = values[i];
                int y = values[i+1];
                values[i] = y;
                values[i+1] = x;
                notsorted = 1;
            }
        }
    }
    while ((notsorted = 0));
    return;
}

What should I be thinking about when fixing it?

EDIT: UPDATED CODE:

EDIT 2: Updated code AGAIN and what the terminal is printing when I try to sort.

Answer 1

ok... As I see it, your outer loop should only execute once. You actually fall in a pretty annoying situation where an absolutely valid and algorithmically correct piece of code is not doing what it is expected. This is because you are using the assignment = instead of the comparison ==. Change the while ((notsorted = 0)) with while (notsorted == 0) and you are good to go.

PS: Also for stylistic purposes I would suggest that you use only one temporary variable so your the swapping code could look like this:

int temp = values[i];
values[i] = values[i+1];
values[i+1] = temp;

I have not tested your code but it seems to be ok...

Good luck!

Edit: I just tested the code and found the algorithmic mistake but I wont give it directly otherwise I would take all the fun away from you. I realised that your outermost loop (while) is testing for the wrong condition. Consider again in which case you want the code to loop again and I am sure you will figure it out. Good luck again! :)

Edit 2: Ok, I know what you did wrong. Its a bit of an annoying mistake. It was one of the first things I thought of to be honest but I tested it on my code and it didn't change anything so I supposed it wasn't that and did not set it back to what you had it. Then I figured out the mistake in the while loop. So my code works :p What you actually do in the initialisation of the for loop is called shadowing. int i = 0, notsorted = 0 actually defines 2 variables i and notsorted. So you are actually defining a new variable within the scope of the for loop called notsorted that variable now shadows the notsorted variable within the scope of main and therefore does not let it change that one, instead changes the one within its own scope which is anyway discarded after the for loop exits. I hope this is not to confusing. The solutions would be to take the notsorted = 0 out of the initialisation of the for loop. That would look like this:

notsorted = 0;
for (int i = 0; i < n-1; i++)
{
...
}

Hope this helps :)

Edit 3: Haha! ok! now I know what you did! You are not running your own code, you are running sort. sort is a bash command that sorts alphabetically (when used without flags) and you will notice that it actually sorts as if the numbers where text :).

You actually need to run your own code.

For a successful search try: ./generate 1000 50 | ./find 2008

For an unsuccessful search try: ./generate 1000 50 | ./find 2013

That should finally do the job! :)