Here we will write a program to implement Bubble Sort in C++, first we will learn what is Bubble sort then we will write the C++ code for the same.

### What is Bubble Sort?

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

**Graphical representation of Bubble Sort:**

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

** Step by Step Example:**

Let us take the array of numbers “5 1 4 2 8”, and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.

**First Pass**

( 5 1 4 2 8 ) to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.

( 1 5 4 2 8 ) to ( 1 4 5 2 8 ), Swap since 5 > 4

( 1 4 5 2 8 ) to ( 1 4 2 5 8 ), Swap since 5 > 2

( 1 4 2 5 8 ) to ( 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 ) to ( 1 4 2 5 8 )

( 1 4 2 5 8 ) to ( 1 2 4 5 8 ), Swap since 4 > 2

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

Now, the array is already sorted, but the 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 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

( 1 2 4 5 8 ) to ( 1 2 4 5 8 )

### Complexity of Bubble Sort:

Bubble sort has worst-case and average complexity both О(n2), where n is the number of items being sorted. There exist many sorting algorithms, such as merge sort with substantially better worst-case or average complexity of O(n log n). Even other О(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.

## Program to implement Bubble sort in C++:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
#include<iostream> using namespace std; int main() { //declaring array int array[5]; cout<<"Enter 5 numbers randomly : "<<endl; for(int i=0; i<5; i++) { //Taking input in array cin>>array[i]; } cout<<"Input array is: "<<endl; for(int j=0; j<5; j++) { //Displaying Array cout<<"\t\t\tValue at "<<j<<" Index: "<<array[j]<<endl; } // Bubble Sort Starts Here int temp; for(int i2=0; i2<=4; i2++) { for(int j=0; j<4; j++) { //Swapping element in if statement if(array[j]>array[j+1]) { temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } // Displaying Sorted array cout<<" Sorted Array is: "<<endl; for(int i3=0; i3<5; i3++) { cout<<"\t\t\tValue at "<<i3<<" Index: "<<array[i3]<<endl; } return 0; } |

### OUTPUT:

Comment if you face any problem or concerns.

## Leave a Reply