CODEWITHSUNDEEP
c++algorithmsortingbubble-sort
ycshao
ycshao

Reputation: 1958

bubble sort algorithm for loop statement warning

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;
}

Upvotes: 4

Views: 417

Answers (4)

H&#233;ctor Asencio L
H&#233;ctor Asencio L

Reputation: 141

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).

Upvotes: 0

yizzlez
yizzlez

Reputation: 8805

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.

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308364

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.

Upvotes: 3

Yu Hao
Yu Hao

Reputation: 122423

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.

Upvotes: 6

Related Questions