Bubble sort is a simple algorithm for sorting, but it’s also quite inefficient, as its worst case is O(n^2) complexity.

But it’s worth learning about it.

We loop through an array, and we keep comparing one item to the one right next to it.

If the item on the right is smaller, we swap the two positions.

Here’s our implementation:

const bubbleSort = (originalArray) => {
  let swapped = false

  const a = [...originalArray]

  for (let i = 1; i < a.length - 1; i++) {
    swapped = false

    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }

    if (!swapped) {
      return a
    }
  }

  return a
}

You can see the O(n^2) comes from the fact that we loop through the array twice to check if we need to swap each item with the one on the right.

We start with the first element and compare it with the second. If the first is larger, we swap them. Otherwise we leave them as-is and move to the second element. We compare it with the third. Again, if the second is larger than the third, we swap them, and we continue until each element finds its position in the array.

Here’s an example:

Suppose we run bubbleSort([2, 1, 3]).

First we compare 2 with 1. 2 is > 1, so we swap them:

1 2 3

then we compare 2 with 3. 2 < 3, so we leave it as-is. We skip the last element, since we know that due to our workflow, it’s always going to be the biggest element.

Lessons in this unit:

0:	Introduction
1:	Linear Search
2:	Binary Search
3:	▶︎ Bubble Sort
4:	Selection Sort
5:	Merge Sort
6:	Quicksort
7:	Algorithm Complexity and Big O Notation