bubble sort algorithm for loop statement warning

Question

I saw a piece of bubble sort code and initially I thought the code is wrong. But after compile and run, it surprised me that it actually works. I want to know how come second statement in the first for loop is not a condition but an assignment. In addition, how come this code will not go into infinitely loop?

PS: It will generate an warning: "suggest parentheses around assignment used as truth value [-Wparentheses]" complaining about the first for loop. Surprisingly it's not an error.

#include <iostream>

void bubblesort(int A[], int n)
{
    for (bool sorted = false; sorted = !sorted; n--)
    {
        for (int i = 1; i < n; ++i)
        {
            if (A[i-1] > A[i])
            {
                int tmp = 0;
                tmp = A[i];
                A[i] = A[i-1];
                A[i-1] = tmp;
                sorted = false;
            }
        }
    }
}

int main()
{
    int a[5] = {1,4,5,2,3};

    bubblesort(a, 5);

    for (unsigned int i = 0; i < 5; ++i)
    {
        std::cout << a[i] << std::endl;
    }

    return 0;
}

Answer 1

The result of an assignment is the left operand, so the condition

sorted = !sorted

is using sorted as the condition after it's assigned a new value. The warning is there to give you a notice that using assignment as condition is sometimes not what you expected. You can use

(sorted = !sorted) == true

to silence the warning.

Answer 2

It's one of the quirks of C and C++ that they allow an assignment in the middle of a statement. Usually it's an error (= instead of ==) so a good compiler will warn you about it.

The value of such an expression is the same as the assigned value.

In this case it's a very tricky optimization; if the value was false it's reset to true and the loop continues, if it was true then it becomes false and the loop termination condition is met. I would never use this in code that anybody was expected to maintain.

Answer 3

An explanation for the code. Basically, if sorted ever is true before the condition the loop will stop.

1st loop: sorted is true

Within the second for loop, it basically checks if the array is sorted. If it isn't sorted -> false and the loop continues. If it is, sorted-> true and execution stops.

Answer 4

The comparision normally is as follows:

sorted != sorted

Of course, this does not make any sense. But instead, you have the following:

sorted = !sorted

By doing this, you just negate the condition for sorting, meaning that the array, which is unsorted, is assumed to be sorted. Then, if you traverse the complete array without making any swap, the left side of the assignment is taken as a condition (which in this case is true).