Algorithms: Bubble Sort with Javascript

Bubble sort is one of the basic sorting algorithms that is taught in every algorithms course. Every software engineer should have a solid understanding of bubble sort. In this quick tutorial, you will learn how to implement bubble sort in Javascript.

How bubble sort works

Bubble sort sorts an unsorted array by iterating through each value in an array and always swapping values if the current value is smaller than the value in the position we look next ([i + 1]). This way, the biggest values "bubble up" at the end of the array and we will eventually get a sorted array as a result. Let's take a closer look with an example.

Example

In the following code example you can see how to sort an unsorted array using bubble sort with Javascript.

const bubbleSort = arr => {
  let len = arr.length;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len; j++) {
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
};

Optimize for nearly sorted input arrays

If our input array is already nearly sorted, we can do a small optimization which will make the algorithm run much faster.

We can do this by adding a noSwaps variable to keep track of if we make any swaps. If we don't do any swaps on a single iteration, we know that the array is already sorted and we can break out of the loop.

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

In this case for example we could already break out of the loop after first iteration which would make the algorithm much faster to execute.

Complexity

In the worst case, time complexity for bubble sort is O(n2).

Bubble sort is a good option if we know that our input data is already nearly sorted.

In other scenarios it might be wise to use a faster sorting algorithm like insertion sort or quick sort instead.