Bubble Sort Algorithm in Java

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.

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