1

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:

UPDATED

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

1
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! :)

12
  • That's not merely a stylistic change, it also affects performance and fault-tolerance. Storing both values in temporary variables makes it easier to recover from a failure mid-swap. Not important in this simple scenario, but worth thinking about for future applications. – Air Oct 10 '14 at 18:41
  • What do you mean? I did not get your point. As a matter of performance it uses 1 variable less, and its anyway released soon after its assignment, also it is probably being compiled into less instructions. And what do you mean that it affects fault-tolerance? I'm a bit confused on which one you consider most appropriate. Unless you mean that the proposed change will increase performance while the original will allow easier fault detection. In which case I agree with you even though in case of an immediate swap that should not be an error-causing statement. – Alexandros Andreou Oct 10 '14 at 19:32
  • Yes, fewer assignments will perform better but be potentially less fault-tolerant. The swap itself may not cause an error but could still be interrupted by errors in another thread. Again, not important here, just an example. – Air Oct 10 '14 at 19:39
  • hm ok... I think we agree. I mainly used the term stylistic as it is used throughout the videos and also, for such low level programing in systems with resources as a modern computer I don't know if it is worth optimising to the level of single variables. Now about the fault detection... I do not completely agree. No information is lost during this process but it might be easier to see things... I won't get further into it as it can become a long pointless discussion. Thank for pointing out though. – Alexandros Andreou Oct 10 '14 at 20:25
  • I tried making the changes you suggested but it's still not working! For example I tried to get it to sort the numbers 49877, 48988, 15165, 1927. It came up with 15165, 1927, 48988, 49877. It does this with bigger sets of numbers too -- seems to sort mostly right, and then put a couple out of place. Any idea what could be going wrong?? thanks so much! – Isabel P Oct 11 '14 at 4:40

You must log in to answer this question.

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