JavaScript Algorithms: Bubble Sort

Bubble sort is often one of the first algorithms you learn when starting out. It’s a simple (but inefficient) way to sort a list of numbers, characters or strings and it could also be adapted to sort other types too.

Here’s how it works. Say you have a list…

[10,9,8,7,6,5,4,3,2,1]

… and you want to sort it so it starts with 1 and ends with 10. With bubble sort you start at the beginning and compare the element at index 0 with the element directly to the right (index 1):

10 is greater than 9 so 10 and 9 should swap

So after the first swap, the list looks like:

[9,10,8,7,6,5,4,3,2,1]

That’s progress! Okay lets do it with the element at index 1.

10 is greater than 8 so 10 and 8 should swap

and we get:

[9,8,10,7,6,5,4,3,2,1]

Rinse and repeat 5 more times…

[9,8,7,6,10,5,4,3,2,1]
[9,8,7,6,5,10,4,3,2,1]
[9,8,7,6,5,4,10,3,2,1]
[9,8,7,6,5,4,3,10,2,1]
[9,8,7,6,5,4,3,2,10,1]
[9,8,7,6,5,4,3,2,1,10]

And 10 is finally sorted to the end of the list!

What happens now? Well, we start all over again. Yeah, pretty tedious, I know:

9 is greater than 8 so 9 and 8 should swap

Rinse and repeat 35 more times…

[8,9,7,6,5,4,3,2,1,10]
[8,7,9,6,5,4,3,2,1,10]
[8,7,6,9,5,4,3,2,1,10]
[8,7,6,5,9,4,3,2,1,10]
[8,7,6,5,4,9,3,2,1,10]
[8,7,6,5,4,3,9,2,1,10]
[8,7,6,5,4,3,2,9,1,10]
[8,7,6,5,4,3,2,1,9,10]
[7,8,6,5,4,3,2,1,9,10]
[7,6,8,5,4,3,2,1,9,10]
[7,6,5,8,4,3,2,1,9,10]
[7,6,5,4,8,3,2,1,9,10]
[7,6,5,4,3,8,2,1,9,10]
[7,6,5,4,3,2,8,1,9,10]
[7,6,5,4,3,2,1,8,9,10]
[6,7,5,4,3,2,1,8,9,10]
[6,5,7,4,3,2,1,8,9,10]
[6,5,4,7,3,2,1,8,9,10]
[6,5,4,3,7,2,1,8,9,10]
[6,5,4,3,2,7,1,8,9,10]
[6,5,4,3,2,1,7,8,9,10]
[5,6,4,3,2,1,7,8,9,10]
[5,4,6,3,2,1,7,8,9,10]
[5,4,3,6,2,1,7,8,9,10]
[5,4,3,2,6,1,7,8,9,10]
[5,4,3,2,1,6,7,8,9,10]
[4,5,3,2,1,6,7,8,9,10]
[4,3,5,2,1,6,7,8,9,10]
[4,3,2,5,1,6,7,8,9,10]
[4,3,2,1,5,6,7,8,9,10]
[3,4,2,1,5,6,7,8,9,10]
[3,2,4,1,5,6,7,8,9,10]
[3,2,1,4,5,6,7,8,9,10]
[2,3,1,4,5,6,7,8,9,10]
[2,1,3,4,5,6,7,8,9,10]

until finally everything is ordered like so:

[1,2,3,4,5,6,7,8,9,10]

And we’re done!

Let’s do it in JavaScript!

There are several bubble sort versions floating around out there but this is probably the most common one.

Step 1: Define the function.

const bubbleSort = (array) => {
  // stuff will go in here
  return array;
}

Step 2: Create a for loop to iterate through each item in the array:

const bubbleSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    // more stuff will go in here  
  }
  return array;
}

Step 3: Add a nested for loop so we can compare each item against other items in the array:

const bubbleSort = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let x = 0; x < array.length - 1 - i; x++) {
      // even more stuff will go in here
    }
  }
  return array;
}

Notice the nested for loop is setup to iterate from index 0 to whatever the index of the outer for loop is minus one. Why? Well, we’ll get to that later. I just wanted you to notice that for now.

Step 4: compare and swap:

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

And that’s it! We’re done!

So let’s say we call the above function like so:

bubbleSort([10,9,8,7,6,5,4,3,2,1])

The inner for loop checks to see if array[x] is greater than array[x + 1]— that is if 10 is greater than 9. Since it is, we swap them using ES6’s destructuring syntax. We then continue iterating until 10 gets pushed all the way to the right:

[9,8,7,6,5,4,3,2,10]

So this function is accomplishing what we talked about earlier. Hooray! But what happens after the inner for loop reaches its termination point (array.length — 1 — i)? Well, the outer for loop continues iterating and whereas array.length — 1 — i resolved to array.length — 1 — 0 in the first outer iteration, on the second it resolves to array.length — 1 — 1. Why? Well if you’ve been paying attention, you’ll know we already asked this ‘why’. Now we’re going to answer it.

Each time the inner for loop iterates, it pushes the largest elements all the way to the right. So after the first loop, we know for certain that the last element in array is the largest element because that element has been either directly or indirectly compared against every other element. Because we know this, there’s no reason to go on comparing other elements against it when the outer for loop does subsequent iterations. So for the sake of efficiency, we concern ourselves with only the part of the list we don’t know about. As a result, at the end of each iteration of the outer for loop, the array used for comparison effectively get’s smaller and smaller:

[9,10,8,7,6,5,4,3,2,1]
[9,8,10,7,6,5,4,3,2,1]
[9,8,7,10,6,5,4,3,2,1]
[9,8,7,6,10,5,4,3,2,1]
[9,8,7,6,5,10,4,3,2,1]
[9,8,7,6,5,4,10,3,2,1]
[9,8,7,6,5,4,3,10,2,1]
[9,8,7,6,5,4,3,2,10,1]
[9,8,7,6,5,4,3,2,1,10]
[8,9,7,6,5,4,3,2,1]
[8,7,9,6,5,4,3,2,1]
[8,7,6,9,5,4,3,2,1]
[8,7,6,5,9,4,3,2,1]
[8,7,6,5,4,9,3,2,1]
[8,7,6,5,4,3,9,2,1]
[8,7,6,5,4,3,2,9,1]
[8,7,6,5,4,3,2,1,9]
[7,8,6,5,4,3,2,1]
[7,6,8,5,4,3,2,1]
[7,6,5,8,4,3,2,1]
[7,6,5,4,8,3,2,1]
[7,6,5,4,3,8,2,1]
[7,6,5,4,3,2,8,1]
[7,6,5,4,3,2,1,8]
[6,7,5,4,3,2,1]
[6,5,7,4,3,2,1]
[6,5,4,7,3,2,1]
[6,5,4,3,7,2,1]
[6,5,4,3,2,7,1]
[6,5,4,3,2,1,7]
[5,6,4,3,2,1]
[5,4,6,3,2,1]
[5,4,3,6,2,1]
[5,4,3,2,6,1]
[5,4,3,2,1,6]
[4,5,3,2,1]
[4,3,5,2,1]
[4,3,2,5,1]
[4,3,2,1,5]
[3,4,2,1]
[3,2,4,1]
[3,2,1,4]
[2,3,1]
[2,1,3]
[1,2]

While the ordered part of the array grows larger and larger:

[]
[]
[]
[]
[]
[]
[]
[]
[]
[10]
[10]
[10]
[10]
[10]
[10]
[10]
[10]
[9,10]
[9,10]
[9,10]
[9,10]
[9,10]
[9,10]
[9,10]
[8,9,10]
[8,9,10]
[8,9,10]
[8,9,10]
[8,9,10]
[8,9,10]
[7,8,9,10]
[7,8,9,10]
[7,8,9,10]
[7,8,9,10]
[7,8,9,10]
[6,7,8,9,10]
[6,7,8,9,10]
[6,7,8,9,10]
[6,7,8,9,10]
[5,6,7,8,9,10]
[5,6,7,8,9,10]
[5,6,7,8,9,10]
[4,5,6,7,8,9,10]
[4,5,6,7,8,9,10]
[3,4,5,6,7,8,9,10]
[1,2,3,4,5,6,7,8,9,10]

There’s one more thing we can do to make this more efficient. We can detect whether or not disorder was found at all at any point after each time the inner for loop terminates. If no disorder was found, we can exit the outer for loop early!

How do we do this? I’m glad you asked. Here’s how:

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

As you can see we added a flag: isOrdered. The flag gets set to true at the start of each iteration of the outer for loop and gets set to false if a swap is needed. This way a mostly ordered array like this one…

[1,2,3,4,5,6,7,8,10,9]

… will only require a total of 17 iterations to order it instead of 45! 9 inner iterations during the outer loops first iteration and 8 inner iterations during the outer loops second iteration. Because order is achieved in the first outer iteration, it gets detected by the second outer iteration and breaks before we enter a third outer iteration.

Solution

So I already gave the solution, but here it is again in color!