CODEWITHSUNDEEP
c++bubble-sort
Diogo Gomes
Diogo Gomes

Reputation: 3

Iterative bubblesort

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?

Upvotes: 0

Views: 382

Answers (2)

Salil Deshpande
Salil Deshpande

Reputation: 105

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.

Upvotes: 1

Skgland
Skgland

Reputation: 981

No, given the description your solution doesn't solve the task.
Yes it is possible.
The following code contains all changes you would need to fix it. 

void bubblesort( int v[], int size ) {  
    boolean change; //create a boolean to track if the current iteration changed anything 
    for( int i = size-1; i >= 0; --i ){  
        change = false; //at the start of each iteration set it to false
        for( int j = 0; j < i; ++j ) {  
            if( v[j] <= v[j+1] ) continue;  
            change = true; // if something changed set it to true  
            int aux = v[j];  
            v[j] = v[j+1];  
            v[j+1] = aux;  
        }  
        if(!change){ // when it's still false at the end of the itteration you are done
            return;
        }
    }
}

Upvotes: 0

Related Questions