Iterative bubblesort

Question

I was doing some exercises in c++, on the topic of sorting algorithms, and I couldn't understand one of them.

It said to implement a function that, given an array of integers, should order them using the bubblesort algorithm (iterative), that should terminate as soon as a for cycle didn't promote an exchange of elements. Is this even possible?

The way I understand it, a normal condition for terminating the algorithm would be to have the sorting be equal to one. So, in this example,

void bubblesort( int v[], int size ) {
    for( int i = size; i > 0; --i )
        for( int j = 0; j < i; ++j ) {
            if( v[j] <= v[j+1] ) continue;
            int aux = v[j];
            v[j] = v[j+1];
            v[j+1] = aux;
         }
}

But this doesn't solve the exercise, does it?

Answer 1

From what I get of your question, you need to terminate the sorting once the inner for loop does not carry out any exchange. This can be done with the help of a bool, as follows:

void bubblesort(int v[], int size)
{
    bool flag;

    for (int i = size; i > 0; --i)
    {
        flag = true;

        for (int j = 0; j < i; ++j)
        {
            if (v[j] <= v[j + 1]) continue;

            flag = false;

            int aux = v[j];
            v[j] = v[j + 1];
            v[j + 1] = aux;
        }

        if (flag) break;
    }
}

Explanation: If the inner if condition is not satisfied, then the value of flag is changed. If for every iteration the if is satisfied, then the value of flag does not change, which is checked at the end of outer loop.