Bubble Sort in JavaScript

02/20/20191 Min Read — In JavaScript, Computer Science

I'm working on learning data structures and different algorithms.

One of the first ones is Bubble Sort:

const bubbleSort = array => {
  let noSwaps
  for (let i = array.length; i > 0; i--) {
    noSwaps = true
    for (let j = 0; j < i - 1; j++) {
      if (array[j] > array[j + 1]) {
        ;[array[j], array[j + 1]] = [array[j + 1], array[j]]
        noSwaps = false
      }
    }
    if (noSwaps) break
  }
  return array
}

Bubble Sort takes O(n^2) time in the worst case because you have two nested loops.
This is a slightly optimized version from Colt Steele's course.
It stops the outer loop when no swaps in the inner loop occur - when the first item in the inner loop is lower than the second item. That means that those two items are already sorted and we can stop.

from Toptal:

Bubble sort has many of the same properties as insertion sort, but has slightly higher overhead. In the case of nearly sorted data, bubble sort takes O(n) time, but requires at least 2 passes through the data (whereas insertion sort requires something more like 1 pass).

Further Reading