Rise To The Top
Sorting Algorithms: Bubble Sort — JavaScript
Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list.
This simple algorithm performs poorly in real world use and is used primarily as an educational tool. (Wikipedia)
Bubble Sort is not often used in production code because it uses a nested loop, producing a time complexity of O(n²). Although it is a highly time-consuming and inefficient sorting algorithm, it is still good to learn. “Why?”, you might ask. It mimics the way we generally think about sorting — by comparing.
Rise ‘N Shine
Given an array of N elements, Bubble Sort will:
- Compare a pair of adjacent items (a, b).
- Swap that pair if the items are out of order (when a > b).
- Repeat steps 1 and 2 until the end of the array is reached (the last pair is the (N-2)-th and (N-1)-th items).
- Now that the largest item is at the last position, reduce N by 1 and repeat steps until N = 1.
Bubble Sort can be optimized by using a boolean variable to check if no swaps were made during the pass. If no swaps were made, the loop can be broken because the array is sorted.
Rise Up
To swap the 2 elements, we could:
- use a
tempvariable and assign one of the elements to it:
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp- use ES2015 syntax
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]- use a helper method (with either syntax)
const swap = (arr, idx1, idx2) => {
[arr[idx1], arr[idx2]] = [arr[idx2], arr[idx1]]
}Let’s look at an example in JavaScript:
Sample Problems
📚 Resources 👀
JavaScript: Bubble Sort algorithm
Implementing Bubble Sort in Javascript
Udemy — JavaScript Algorithms and Data Structures Masterclass
