Bubble Sort is a simple linear algorithm that loops through a dataset comparing elements that are side-by-side and swapping their order if the next value is smaller than the current one.
Here's a description from Wikipedia:
Bubble 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.
We're going to implement the Bubble Sort algorithm in JavaScript below.
Hey, Tyler here. I'm currently working on some great web development and digital marketing products and services over at ZeroToDigital.
If that sounds interesting to you, please check it out!
We need 1 helper function for our algorithm that will be in charge of swapping the 2 items in our dataset.
JavaScript
swap = (array, i, j) => {
var temp = array[i]
array[i] = array[j]
array[j] = temp
}The swap function is pretty straight-forward. It receives an array of our dataset and 2 index values i and j. Then it swaps the 2 values.
JavaScript
bubbleSort = array => { // O(n2)
if (array.length <= 1) return array
var swapped = true
while (swapped) {
swapped = false
for (var i = 0; i < array.length; i++) {
if (array[i] && array[i + 1] && array[i] > array[i + 1]) {
swap(array, i, i + 1)
swapped = true
}
}
}
return array
}The bubbleSort function takes the array of our dataset and returns the sorted array. First, it checks that the dataset is not of 1 value or less (because then sorting would be unnecessary), then it creates a variable of swapped and sets it value to true.
We'll then create a loop that will run while the value of swapped is true. Inside the loop, we'll first set swapped to false by default (which would end our loop unless it's returned to true), then we'll run through our dataset and check if the current value is greater than the next value. If it is, we'll call the swap function to swap the 2 values and change the swapped variable to true signifying that we need to repeat our loop at least one more time (we'll continue with our algorithm until we've made a full clean loop through the dataset).
JavaScript
var array = [8,3,5,9,1,5,9,2,3,8,4]
bubbleSort(array)
// 3,8,5,9,1,5,9,2,3,8,4
// 3,5,8,9,1,5,9,2,3,8,4
// 3,5,8,9,1,5,9,2,3,8,4
// 3,5,8,1,9,5,9,2,3,8,4
// 3,5,8,1,5,9,9,2,3,8,4
// 3,5,8,1,5,9,9,2,3,8,4
// 3,5,8,1,5,9,2,9,3,8,4
// 3,5,8,1,5,9,2,3,9,8,4
// 3,5,8,1,5,9,2,3,8,9,4
// 3,5,8,1,5,9,2,3,8,4,9
// 3,5,8,1,5,9,2,3,8,4,9
// 3,5,8,1,5,9,2,3,8,4,9
// 3,5,8,1,5,9,2,3,8,4,9
// 3,5,1,8,5,9,2,3,8,4,9
// 3,5,1,5,8,9,2,3,8,4,9
// 3,5,1,5,8,9,2,3,8,4,9
// 3,5,1,5,8,2,9,3,8,4,9
// 3,5,1,5,8,2,3,9,8,4,9
// 3,5,1,5,8,2,3,8,9,4,9
// 3,5,1,5,8,2,3,8,4,9,9
// 3,5,1,5,8,2,3,8,4,9,9
// 3,5,1,5,8,2,3,8,4,9,9
// 3,5,1,5,8,2,3,8,4,9,9
// 3,1,5,5,8,2,3,8,4,9,9
// 3,1,5,5,8,2,3,8,4,9,9
// 3,1,5,5,8,2,3,8,4,9,9
// 3,1,5,5,2,8,3,8,4,9,9
// 3,1,5,5,2,3,8,8,4,9,9
// 3,1,5,5,2,3,8,8,4,9,9
// 3,1,5,5,2,3,8,4,8,9,9
// 3,1,5,5,2,3,8,4,8,9,9
// 3,1,5,5,2,3,8,4,8,9,9
// 3,1,5,5,2,3,8,4,8,9,9
// 1,3,5,5,2,3,8,4,8,9,9
// 1,3,5,5,2,3,8,4,8,9,9
// 1,3,5,5,2,3,8,4,8,9,9
// 1,3,5,2,5,3,8,4,8,9,9
// 1,3,5,2,3,5,8,4,8,9,9
// 1,3,5,2,3,5,8,4,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,5,2,3,5,4,8,8,9,9
// 1,3,2,5,3,5,4,8,8,9,9
// 1,3,2,3,5,5,4,8,8,9,9
// 1,3,2,3,5,5,4,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,3,2,3,5,4,5,8,8,9,9
// 1,2,3,3,5,4,5,8,8,9,9
// 1,2,3,3,5,4,5,8,8,9,9
// 1,2,3,3,5,4,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9
// 1,2,3,3,4,5,5,8,8,9,9As you can see, there are a lot of loops required, including an additional loop through the entire dataset at the end just to verify the correct order. Bubble sort is a stable sorting algorithm, however, it's time complexity isn't very good at O(n^2). It does have an efficient space complexity of O(1), however, so it may be a sorting algorithm that would work for you or your program if you're not dealing with a large dataset and you're looking to keep memory usage at a minimum.
Check out other sorting algorithm implementations in JavaScript: