Firstly, let's get it out of the way. When we say "sort", the idea is to re-arrange the elements such that they are in ascending order.
Table of Contents
- Explanation of Bubble Sort
- Complexity of Bubble Sort
- Other Related Concepts
Explanation of Bubble SortIf you are a newbie to sorting, Bubble sort is a great place to start! It is one of the more intuitive sorting methods as its algorithm mirrors how our brain generally thinks about sorting - by comparing.
Let's remove the vagueness and delve deeper into it.
A. What Bubble Sort Does?To achieve sorting in Bubble Sort, the adjacent elements in the array are compared and the positions are swapped if the first element is greater than the second. In this fashion, the largest value "bubbles" to the top.
Usually, after each iteration the elements furthest to the right are in correct order. The process is repeated until all the elements are in their right position.
B. What Bubble Sort Does?1. Starting with the first element, compare the current element with the next element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, just move to the next element.
4. Start again from Step 1.
C. Illustrating the Bubble sort methodIteration 1: [6,4,2,5,7] → [4,6,2,5,7] → [4,2,6,5,7] → [4,2,5,6,7] → [4,2,5,6,7]
Iteration 2:[4,2,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]
Iteration 3: [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7] → [2,4,5,6,7]
Other AlternativesAs you might have noticed, Bubble Sort only considers one element at a time. Thus, it is highly time consuming and inefficient. Due to its inefficiency, bubble sort is almost never used in production code.
You can use a built in function Array.prototype.sort() for sorting. This is an inplace algorithm just like bubble sort which converts the elements of the input array into strings and compares them based on their UTF-16 code unit values. Also, if you are interested, you can read about index sort which is another simple comparison based sort method that has a better performance than Bubble sort.
As you can see here, the sorting function will run until the variable "i" is equal to the length of the array. This might not be the most efficient solution as it means the function will run on an already sorted array more than once.
A slightly better solution involves tracking a variable called "checked" which is initially set to FALSE and becomes true when there is a swap during the iteration. Running this code on a do while loop to run the sorting function only when "checked" is true ensures that the function will not run on a sorted array more than once.
VisualizationIf you are finding it hard to visualize Bubble Sort, you can check this website https://visualgo.net/bn/sorting?slide=1.
You can play around with the code and see the specific function of each part of the code and how they play together to get the final sorted array.
Complexity of Bubble SortThe worst case scenario: quadratic O(n²): this is the case when every element of the input array is exactly opposite of the sorted order.
Best case scenario: linear O(n): when the input array is already sorted. Even in this case, we have to iterate through each set of numbers once.
The space complexity of Bubble Sort is O(1).