In this article we will discuss about what is bubble sort, why it is considered as one of the simplest sorting algorithm, what its complexity, how we can improve the bubble sort algorithm.
What is bubble sort??
- Bubble sort is one of the simplest sorting algorithms.
- Bubble sort compares each pair of adjacent items and swaps them if they are in the wrong order.
- The pass through the list is repeated until no swaps are needed, that means array is sorted.
- As the name indicates, the lighter elements (smaller) ‘bubble up’ to the top.
- Bubble sort is also known as sinking sort (heavy or bigger elements settles down at the bottom of the list after each iteration).
Time Complexity: O(N2)
Let’s walk through on example:
- Pros: Bubble sort algorithm is considered as very simple sorting technique since all you need to do is compare all the adjacent elements and swap them if they are in wrong order.
- Cons: Main drawback of bubble sort is its time complexity which is O(N2) since all the pairs are compared, even when the original array is sorted.
Java Code for Bubble Sort:
Original Array: [5, 1, 9, 3, 2, 10] Sorted Array: [1, 2, 3, 5, 9, 10]
How we can improve Bubble sort:
- As see in the program above, bubble sort compares all the pairs in the array, even when original array is sorted or partially sorted. This is where we can do some improvements.
- During any iteration, if there are no swaps then we can claim that our array is already sorted.
Java code for Optimized Bubble Sort:
Original Array: [5, 1, 9, 3, 2, 10] Sorted Array: [1, 2, 3, 5, 9, 10] ------------------------------ Original Array: [1, 2, 4, 6, 8, 10] Sorted Array: [1, 2, 4, 6, 8, 10]