Implementing a Bubble Sort Algorithm in JavaScript

Welcome to the third entry in my Sorting Algorithms in JS series here on Dev! I've previously covered both Selection Sort and Insertion Sort in previous posts, so check those out if you'd like to learn more about sorting algorithms in JS.

Intro

In computer science, few tools are used quite as often as sorting algorithms. We rely on them every day as programmers and engineers to sift through data, and they're built into nearly every modern programming language in one way or another.

While using a language's built-in sorting functions may get the job done for most day-to-day work, it's important to understand what's going on under the hood, and what different sorting algorithms are actually doing and why they work the way they do. While it may not come up often, there's always the chance you may be asked to implement or explain a sorting algorithm in a technical interview setting, which is exactly what this post is here to prepare you for!

Today, we'll be looking at Bubble Sort, another one of the main sorting algorithms in Computer Science.

What is Bubble Sort?

The Wikipedia page on Bubble Sort describes the algorithm as follows:

Bubble sort, sometimes referred to as sinking 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.

From the standpoint of an educational tool, Bubble Sort is actually one of the simplest sorting algorithms to comprehend and implement. Unfortunately it's also one of the least efficient, and is almost never used in practical programming applications.

Essentially, the algorithm iterates over an array multiple times (or once, in the edge case of an array already being sorted), comparing each element to the element to the right of it and swapping them so that the greater element is to the right. This essentially "bubbles up" the greatest value to the end of the array each time the iterative loop runs, slowly but surely putting the values in their proper sorted positions.

Here's a helpful visual representation of what happens while the algorithm is running:

As you can see, each iteration swaps greater values to the right multiple times until the greatest value in the array is found, which will then be swapped all the way to the end. Simple, but it gets the job done!

How efficient is it?

Unfortunately, "getting the job done" isn't the only requirement for a sorting algorithm. As I mentioned before, Bubble Sort is notoriously slow and inefficient, relegating it to being mostly used as an educational tool rather than a practical one. Other sorting algorithms like Quick Sort, Heap Sort, or Merge Sort should always be used instead for most practical purposes.

One advantage that Bubble Sort has over other sorting algorithms is that its core logic has a built-in check to see if an array is already sorted, resulting in an O(n) runtime if a sorted array is passed in, since only one iteration through the array will be required. However, this could be considered an edge "best case" rather than a norm, and while other algorithms might take longer to check for an already sorted array, the overall inefficiency of Bubble Sort still loses out.

Bubble Sort has a worst case and average case runtime complexity of O(n^2), and a space complexity of O(n).

How do we implement it?

Now that I've successfully sold you on Bubble Sort (or made you want to steer clear of it forever), let's get down to implementing it in code!

The final JavaScript code will look like this:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
  return array;
}

Let's break it down into pieces.

First off, let's declare the function and our return value (the sorted array, modified in-place):

function bubbleSort(array) {

return array;
}

Next, we'll declare a very important variable, isSorted, and set it to a false boolean value:

function bubbleSort(array) {
  let isSorted = false;

  return array;
}

Now this might seem strange, since we don't know if the passed in array is sorted or not, but it'll quickly make sense. Essentially what we're doing is setting the value to false to start, and using that as a way to escape from the while loop that we'll be putting all of our logic inside of, like so:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;

  }
return array;
}

As you can see, the while loop is set to continue running as long as !isSorted returns true-- aka as long as isSorted === false.

Every time the loop begins we set the value to true, which will stop the loop from running. How does this help us? Well, in our next step of logic, we'll iterate through the array and set isSorted back to false if we perform any swaps. This means that as long as there is at least one swap performed, the loop will continue running. Finally, on the last iteration through the sorted array, the isSorted value will remain true, and the while loop will end.

Sound a little confusing? Let's see it in code:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

Let's focus in on the section we just added:

for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i + 1]) {
    [array[i], array[i + 1]] = [array[i + 1], array[i]];
    isSorted = false;
  }
}

This for loop iterates through the array up until 1 value before the end (array.length - 1), and compares every element's value to the element directly to the right of it (i + 1.)

If you remember the original description and visualization of the algorithm from earlier, this is the part where we now swap values and "bubble up" elements of the array. In this tutorial we're using JavaScript ES6+ syntax to swap elements using the [a, b] = [b, a] format.

If the value on the left is greater than the value to its right, we swap the two elements and set isSorted to false, since we know that the array isn't fully sorted on this loop through the array.

Now we put it all back together again for the finished algorithm:

function bubbleSort(array) {
  let isSorted = false;
  while (!isSorted) {
    isSorted = true;
    for (let i = 0; i < array.length - 1; i++) {
      if (array[i] > array[i + 1]) {
        [array[i], array[i + 1]] = [array[i + 1], array[i]];
        isSorted = false;
      }
    }
  }
return array;
}

And we're done!

Let's walk through the logic one more time.

1. We initialize isSorted to false.
2. Our while loop runs perpetually until isSorted is equal to true, in which case it stops.
3. Every time the while loop begins, isSorted is set to true, so that if no swaps are performed in the for loop the while loop will end.
4. In our for loop, we iterate through the entire array and compare values. If a value is greater than its neighbor to the right, we swap the two and proceed (and set isSorted to false.)
5. We repeat the while loop, iterating through the array multiple times until it's completely sorted, and then return the sorted array.

I recommend looking at this handy visualization again to help lock in the logic:

If you've come this far, thanks so much for reading! I hope this was a helpful tutorial to anyone learning about sorting algorithms, JavaScript, or programming fundamentals in general. 😄

I'll continue working through more sorting algorithms in future posts, so stay tuned!