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.

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.

Generally, insertion sort has better performance than bubble
sort.

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!...

Thanks for studying today!...

Very much useful article. Kindly keep blogging

ReplyDeleteJava Training in Chennai

Java Online Training India