CODEWITHSUNDEEP
c++algorithmsortingdata-structuresbubble-sort
user11432525
user11432525

Reputation:

What is the use of the outer loop (i loop) in the bubble sort algorithm?

    int main() {
        int arr[5];
        for ( int i = 0; i < 5; i++) {
            cin>>arr[i];
        }
        for (int i = 0; i < 5; i++) {
            for ( int j = 1; j < 5; j++) {
                if ( arr[j] < arr[j-1]) swap(arr[j], arr[j-1]);
            }
        }
        
        for( int i = 0; i < 5; i++) cout<<" "<<arr[i]<<" "<<endl;
    }
    
    /* take an element then if the adjacent element is smaller, replace it with that and repeat this process */

I tried removing the j loop and replace j, j-1 with i, i-1 but it throws an error which I am not able to figure out, this is bubble sort algo. I want to understand what is the use of two loops there.

Upvotes: 0

Views: 261

Answers (2)

Alberto Casas Ortiz
Alberto Casas Ortiz

Reputation: 895

The bubble sort algorithm consist in sinking each number till it reaches its position. For doing this, the inner loop (j loop) swaps each pair of adjacents numbers. For assure that the full list is ordered, you need to repeat this process a specific number of times.

In the worst case (reversed order), the algorithm has to repeat the swapping process at least n times (one per each element in the list), the outer loop (i loop), takes care of it.

So, the inner loop (j loop) swaps pairs of adjacent elements, and the outer loop (i loop) assures that the swapping process is repeated at least n times. (If the list is ordered before reaching n iterations in the outer loop, you can stop the algorithm saving time).

Upvotes: 2

Lazini
Lazini

Reputation: 43

This bubble sort algorithm works like so: find the element with the maximum value, and place it at the end of your arr list. Then find the next element with the maximum value, and place it right before the previous value. And so on, and so forth.

Removing the second for loop (the one with j), means you'll only find the first maximum value once, and place it at the end.

Hence, the use of the second for loop is to find each next maximum value, and place them in order.

Upvotes: 0

Related Questions