Bubble
Sort is the simplest sorting algorithm. It works by iterating the input array
from the first element to last, comparing each pair of elements and swapping
them if needed.
It continues
its sort until no swaps are needed. The algorithm got its name the way smaller
elements “bubble” to the top of the list.

The only **advantage **of bubble sort over other implementation is
that it can detect whether the input is already sorted or not. Also known as comparison sort.

Let take an array of input:

**1 5 4 2 8**

In first loop, it will iterate the entire element from 0^{th}
index to 4^{th} index

__Pass 1: __

**1 5**** 4 2 8
-> **1 5** 4 2 8 ** no swap because 1>5 fails

**1 5 4 2 8 -> 1 4 5 2 8 **no swap because 5>4 fails

**1 4 5 2 8 -> 1 4 2 5 8 **no swap because 5>2 fails

**1 4 2 5 8 -> 1 4 2 5 8** no swap

__Pass 2__

**1 4**** 2 5 8
-> 1 4 2 5 8 **no swap

**1 4 2 5 8 -> 1 2 4 5 8 **swap occur because 4>2

**1 2 4 5 8 -> 1 2 4 5 8 **no swap** **

__Pass 3: __

**1 2**** 4 5 8
-> 1 2 4 5 8 **no swap

**1 2 4 5 8 -> 1 2 4 5 8 **no swap

__Pass 4:__

**1 2**** 4 5 8
-> 1 2 4 5 8 **no swap

**Output**:

**1 2 4 5 8**

If you see above, when the array is already sorted it will iterate over the array that why this algorithm complexity is O(n^2) **even** in best case.

We can improve it by using one Boolean flag. When there is
no swap means array is already sorted, then we can skip the remaining process.

This modified version improved the best cast of bubble sort to O(n).

**Performance **:

- Worst Case Complexity : O(n^2)
- Best Case Complexity (improved) : O(n)
- Average Case Complexity : O(n)

If you know anyone who has started learning Java, why not help them out! Just share this post with them.

Thanks for studying today!...