**Bubble Sort** is the simplest sorting algorithm that works by repeatedly comparing the adjacent elements and swapping them if they are in the wrong order. The swapping & passes through a list are repeated until all the elements are not sorted.

The best-case time complexity of Bubble Sort is O(N) and occurs when all the elements in the list are in sorted order, but in the worst case, the complexity becomes O(N²)

### Working of Bubble Sort

Let’s understand how the bubble sort works by taking the unsorted array with elements [15 11 14 12 18]

**First Pass**

(**15 11** 14 12 18) => (**11 15** 14 12 18), since 15 is greater than 11, so we will swap 15 & 11.

(11 **15 14** 12 18) => (11, **14 15** 12 18), since 15 > 14, swap 15 & 14

(11 14 **15 12** 18) => (11 14 **12 15** 18), since 15 > 12, swap 15 & 12

(11 14 12 **15 18**) => (11 14 12 **15 18**), 15 < 18, hence no swapping

**Second Pass**

(**11 14** 12 15 18) => (**11 14** 12 15 18)

(11 **14 12 **15 18) => (11 **12 14** 15 18), since 14 > 12, swap 14 & 12

(11 12 **14 15 **18) => (11 12 **14 15** 18)

(11 12 14 **15 18**) => (11 12 14 **15 18**)

Now, the array is already sorted, but the algorithm doesn’t know. Hence it will run one more pass without any swap to know it is sorted

**Third Pass**

(**11 12** 14 15 18) => (**11 12 **14 15 18)

(11 **12 14** 15 18) => (11 **12 14** 15 18)

(11 12 **14 15 **18) => (11 12 **14 15** 18)

(11 12 14 **15 18**) => (11 12 14 **15 18**)

This is how the bubble sort will works.

### Algorithm

BubbleSort(arr, size){//boolean varible to check if elements are swappedswapped = false; for i in range(0 to size-1){//start with assumption that no elements are swappedswapped = false;for j in range(0 to size-i-1){ if(arr[j]>arr[j+1]){//if element are swapped the mark swapped trueswap(arr[i], arr[j]); swapped = true; }/*if no elements are swapped, it meansthe is now sorted */if(swapped == false) break; } } return }

### Implementation of the above algorithm is CPP

#include <bits/stdc++.h> using namespace std; void swap(int *a, int *b){ int temp; temp = *a; *a = *b; *b = temp; } int bubble_sort(int *arr, int size){ bool swapped; int i,j; for(i=0; i<size-1; i++) { swapped = false; for(j=0; j<size-i-1; j++) { if(arr[j]>arr[j+1]) { swap(&arr[j], &arr[j+1]); swapped = true; } } if(swapped == false) break; } return 0; } int main(){ int arr[] = {15, 11, 14, 12, 18}; int arr_size = sizeof(arr)/sizeof(arr[0]); bubble_sort(arr, arr_size); cout<<"Sorted array is:"<<endl; for(int i=0; i<arr_size; i++) cout<<arr[i]<<" "; cout<<endl; return 0; }

###### Output

Sorted array is: 11 12 14 15 18

### Time complexity

The time complexity of BubbleSort is O(N²) in the worst case because in worst case we have to compare every element with every other element N time, where N is number of elements in the array. The best-case time complexity is O(N) and the sorted array only will result in best-case complexity.

**Bubble Sort properties at a glance:**

1. Best case time complexity = **O(N)**

2. Worst-case time complexity = **O(N²)**

3. Auxiliary space requirement =** O(1)**

4. Number of comparisons required = **O(N²)**

5. BubbleSort is an **in-place** sorting algorithm

6. Bubble Sort is a **stable sort**

Did, we miss something, or do you want to add some other key points?

Please comment.