Bubble Sort With Example - How To Implement Bubble Sort

Prashant | Tue, 02 Jun, 2020 | 393

Bubble sort with Example

Bubble sort is a very simple algorithm to sort elements. It compares adjacent elements to check if they are in order or not, if they are not in order it will get swapped and sorted.

This is also called stable sorting as similar values do not change their respective places and they stays in order.

Explanation of bubble sort

First Pass:
5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

 

Second Pass:
1 4 2 5 8 ) –> ( 1 4 2 5 8 )
( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

 

Third Pass:
1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )
( 1 2 4 5 8 ) –> ( 1 2 4 5 8 )

 

Implementing Bubble Sort Algorithm

Following are the steps involved in bubble sort(for sorting a given array in ascending order):

  1. Starting with the first element(index = 0), compare the current element with the next element of the array.
  2. If the current element is greater than the next element of the array, swap them.
  3. If the current element is less than the next element, move to the next element. Repeat Step 1.

 

Code for bubble sort

#include <bits/stdc++.h>
 
using namespace std;

int main(int argc, char** argv)
{
    int size=5;
    int arr[size]={5,1,4,2,8};
    for(int index=0;index<size-1;index++){
        for(int ctr=0;ctr<size-index-1;ctr++){
            if(arr[ctr]>arr[ctr+1]){
                swap(arr[ctr],arr[ctr+1]);
            }
        }
    }
    
    for(int index=0;index<size;index++)
    cout<<arr[index]<<" ";
}

Output 

{5,1,4,2,8} -> {1,2,4,5,8}

0 comments
Leave a comment