Table of contents:-
What is Bubble Sort?
Bubble sort is a fundamental sorting technique used in programming. The bubble sort algorithm moves through the whole dataset multiple times rearranging them into ascending or descending order.
The algorithm compares an element with the element adjacent to it and if the element is greater than the element next to it, they are swapped (if the required overall arrangement is ascending). In this article, we will always consider the arrangement required as ascending.
After every single traversal of the dataset, the element which is the greatest gets automatically placed at the end of the list. Note that after every traversal, the last element is not included in the list that will be considered for sorting in the next traversal.
For example if a list is [1,3,4,2,7,5]. The algorithm will first compare 1 and 3. Since 1<3, no swapping occurs. Similarly for 3 and 4 as well.
When the algorithm arrives at 4 and 2, since 4>2, they will be swapped and the list will become [1,3,2,4,7,5]. Further, no swapping occurs at 4 and 7, but occurs at 7 and 5. Hence, after a single traversal, the list becomes [1,3,2,4,5,7]. Notice that the largest element 7 automatically arrives at the last place. For the next traversal, the algorithm will only consider the list as [1,3,2,4,5] neglecting the 7 and will then perform bubble sort on the new list.
If you choose to swap elements when the element is smaller than the element next to it, the list will return in descending order.
Benefits and pitfalls of Bubble Sort
One of the strongest positives about Bubble Sort is its lack of complexity. It is a fairly simple algorithm to code. The only major task to perform is the comparison of two elements and swapping them if they satisfy the required criteria.
Bubble Sort however is not considered efficient for large pieces of data as it takes a lot of time. In computer programming terms, bubble sort has a time complexity of O(n logn) (n is the number of elements in the dataset) which is not considered very good for efficient coding.
Q: What does Bubble sort mean?
A: Bubble sort is named so because of the elements “bubble” to the top in the dataset. Bubble sort is also called sinking sort for the opposite reason as some elements of the dataset sink to the bottom as well.