What is Bubble Sort and How to Implement it in JavaScript

Bubble sort is a sorting algorithm that works by comparing adjacent elements and swapping them if they are in the wrong order. The algorithm will keep looping until it finishes an entire pass without making any more swaps.

Due to it's simplicity, it is often used to demonstrate the concept of a sorting algorithm. However, it has little use outside of the conceptual because of it's terrible performance.

Bubble sort has a worst case complexity of O(n^2) and, if the input is already sorted, a best case complexity of O(n).

Step-by-Step Example

Here is a visual breakdown of a bubble sort from the lowest number to the greatest number using the array '3, 9, 5, 1, 2'. Elements in bold are being compared.

First Pass

(3 9 5 1 2) => (3 9 5 1 2), No change as the two elements are already in the correct order.

(3 9 5 1 2) => (3 5 9 1 2), swap because 9 > 5.

(3 5 9 1 2) => (3 5 1 9 2), swap because 9 > 1.

(3 5 1 9 2) => (3 5 1 2 9), swap because 9 > 2.

Second Pass

(3 5 1 2 9) => (3 5 1 2 9)

(3 5 1 2 9) => (3 1 5 2 9), swap because 5 > 1.

(3 1 5 2 9) => (3 1 2 5 9), swap because 5 > 2.

(3 1 2 5 9) => (3 1 2 5 9)

Third Pass

(3 1 2 5 9) => (1 3 2 5 9), swap because 3 > 1.

(1 3 2 5 9) => (1 2 3 5 9) swap because 3 > 2.

(1 2 3 5 9) => (1 2 3 5 9)

(1 2 3 5 9) => (1 2 3 5 9)

The array is sorted by the end of the third pass, but the algorithm needs one whole pass without any swaps before it can finish.

Fourth Pass

(1 2 3 5 9) => (1 2 3 5 9)

(1 2 3 5 9) => (1 2 3 5 9)

(1 2 3 5 9) => (1 2 3 5 9)

(1 2 3 5 9) => (1 2 3 5 9)

Javascript Implementation

Here in one way to implement a bubble sort using JavaScript.

1const startingArray = [3, 9, 5, 1, 2]
2
3function bubbleSort(arr) {
4  let finished = false // exit condition
5  let tempArr = Array.from(arr) // make a copy of our starting array
6
7  while (!finished) {
8    for (let i = 0; i < tempArr.length - 1; ) {
9      let first = tempArr[i]
10      let second = tempArr[i + 1]
11
12      // set exit condition at start of loop
13      if (i === 0) {
14        finished = true
15      }
16
17      // swap if first element is greater than the second element
18      if (first > second) {
19        // swap using ES6 destructuring!
20        ;[tempArr[i], tempArr[i + 1]] = [tempArr[i + 1], tempArr[i]]
21        finished = false
22      }
23
24      // repeat loop if an item was swapped
25      if (finished === false && i === tempArr.length - 2) {
26        console.log("Starting the loop again!")
27        i = 0
28      } else {
29        i++
30      }
31    }
32  }
33  return tempArr
34}
35
36bubbleSort(startingArray) // [1, 2, 3, 5, 9]

Just because bubble sort doesn't have any practical applications outside of academia doesn't mean I didn't have a good time writing my own implementation. I came away from this exercise really appreciating the brevity of the built-in array method .sort().

Cheers!

Find a mistake? Help me fix it by submitting a pull request.