### Bubble Sort

The basic idea of bubble sort is to compare two adjoining values and exchange them if they are not in proper order.

Given an array of length N then iterate over N-1 times because if we sorted N-1 elements then the last elements are automatically getting its appropriate position. In every iteration N-1-i comparison is done (where i is the iteration value over N-1 elements) because in each iteration the N-1-i position is get its appropriate element.

PASS 1 :

PASS 2 :

PASS 3 :

PASS 4:

PASS 5:

PASS 6:

According to above fig unsorted array is to be sorted in ascending order. Where N is total number of elements in the given array which is 7. The index of the array is starting from 0 so, we iterate N-2 which is 5 times over the array.

Note : If we take the index of the array from 1 to n then we iterate over N-1 times over the array.

**Iteration 1**: We compare 13 & 24 where 13 is less than 24 so no change is done. In second comparison (between 24 and 5) 24 is greater than 5 (24>5) so swapping is done. Similarly, third, fourth, fifth and sixth comparison is done. After sixth comparison we get the largest element at the last position (N-1-i position) of the array. So, we do not want to done comparison again for sixth and seventh position as seventh position gets its appropriate element.

**Iteration 2**: Five comparisons are done which is nothing but N-1-i (where N =7 and i =2 as 2^{nd} iteration).

After fifth comparison we get second largest number comes at its appropriate position. So, we do not want to done comparison again for fifth and sixth position as sixth position gets its appropriate element.

**Iteration 3**: Four comparisons are done which is nothing but N-1-i (where N =7 and i =3 as 3^{rd} iteration).

After fourth comparison we get next largest number comes at its appropriate position. So, we do not want to done comparison again for fourth and fifth position as fifth position gets its appropriate element.

**Iteration 4**: Three comparisons are done which is nothing but N-1-i (where N =7 and i =4 as 4^{th} iteration).

After third comparison we get next largest number comes at its appropriate position. So, we do not want to done comparison again for third and fourth position as fourth position gets its appropriate element.

**Iteration 5**: Two comparisons are done which is nothing but N-1-i (where N =7 and i =5 as 5^{th} iteration).

After second comparison we get next largest number comes at its appropriate position. So, we do not want to done comparison again for second and third position as third position gets its appropriate element.

**Iteration 6**: One comparison is done which is nothing but N-1-i (where N =7 and i =6 as 6^{th} iteration).

After first comparison we get next largest number comes at its appropriate position. So, we do not want to done comparison again for first and second position as second position gets its appropriate element.

After sixth iteration we get sorted array in ascending order because the first position is automatically gets it appropriate element.

**Code :-**

#include<iostream> using namespace std; void bubbleSort(int arr[],int n){ for(int i=0;i<n-1;i++){ //Iterate over the array i.e N-1 iteration for(int j=0;j<n-1-i;j++){ //Comparisons in each iteration i.e. N-1-i if(arr[j]>arr[j+1]&&arr[j]!=arr[j+1]){ //Compare the adjacent elements swap(arr[j],arr[j+1]); //Swap the elements if they are not in appropriate position } } } } int main(){ int n; cin>>n; int arr[n]; for(int i=0;i<n;i++){ //Enter the elements of unsorted array cin>>arr[i]; } bubbleSort(arr,n); //Perform bubble sort for(int i=0;i<n;i++){ cout<<arr[i]<<" "; //Display after sorting the array } return 0; }

### Analysis of Bubble sort

Bubble sort is data sensitive sort which means that bubble sort perform differently when :

- Data in sorted order
- Data in reverse sorted order
- Data in random order

We do only one pass when data in sorted order. [**Time Complexity** of 1 pass is **O(1)** ]

So, number of comparisons = (N-1) [N is number of elements in array. So, **Time complexity** of no. of comparisons is **O(N)**]

No swapping is performed as data is already in sorted order.

**Total Time complexity = O(N) **

We do N-1 pass when data in reverse sorted order. [**Time Complexity** of N-1 pass is **O(N)** ]

So, number of comparisons = (N-1)+(N-2)+(N-3)+—————+3+2+1 =N(N-1)/2=N^{2} [N is number of elements in array. So, **Time complexity** of no. of comparisons is **O(N ^{2})**]

Total swaps performed = Number of comparisons =N(N-1)/2

**Total Time complexity = O(N ^{2}) **

We do p pass when data in random order. [**Time Complexity** of p pass is **O(p)** ]

So, number of comparisons = (N-1)+(N-2)+(N-3)+———-+(N-p) =(2pN-p^{2}-p) = p^{2} [N is number of elements in array. So, **Time complexity** of no. of comparisons is **O(p ^{2})**]

**Total Time complexity = O(p ^{2}) [Where p is total number of passes] **

CommentsNo comment yet.