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 0th
index to 4th 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 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
Good Post! Thank you so much for sharing this pretty post, it was so good to read and useful to improve my knowledge as updated one, keep blogging.
ReplyDeletePython Training in electronic city
DataScience with Python Training in electronic city
AWS Training in electronic city
Big Data Hadoop Training in electronic city
Devops Training in electronic city
blockchain Training in electronic city
Hibernate Training in electronic city