loading...
Cover image for Bubble Sort Algorithm Explained By Picking Teams At Recess

Bubble Sort Algorithm Explained By Picking Teams At Recess

kbk0125 profile image Kevin Kononenko ・6 min read

There is a common problem in all coding languages around learning algorithms.

The number of lines of code does not match up with the complexity of the code. It also does not reflect the amount of mental simulation you need to do in order to understand the code!

Here’s what I mean- let’s say that you have a simple 5-10 line algorithm (like bubble sort). This algorithm can be wrapped in a function and then used with pretty much any array.

But, since it is so short, you might assume that it is relatively simple to understand. After all, experienced programmers can read it once and then quickly recognize a simple sorting algorithm.

However, every newbie will read the code, and by line 3, they will realize that it is MUCH more complicated than they anticipated.

In this guide, we will talk about how to understand the bubble sort algorithm, and get around the cognitive traps that make it so difficult to understand.

First of all, let’s get a quick definition out of the way: an algorithm is comprised of multiple lines of code that achieve a specific task.

It’s a pretty wide-ranging definition.

In this example, the bubble sort algorithm is meant to sort a series of elements in an array from smallest to largest.

We are going to do a line-by-line breakdown of bubble sort that uses space and motion to explain what is happening in each line. Your brain uses space and motion to understand the relationship between multiple objects.

Here’s a real-world scenario that you might be familiar with- you and your friends want to play soccer at recess. So, you have to pick teams before you get started.

Bubble sort helps you answer the question:

“Who should be picked first…second…third… etc. out of all the players?”

It looks like this:

So, let’s re-rank these players using bubble sort! Players are ranked on a 1-10 scale.

The Basic Setup of Bubble Sort

Here’s the array that we will use in this example:

let players = [4, 6, 3, 9, 6, 2, 1, 10, 4, 5];

We need to reorder this array from smallest to largest. So, if we want to get the player ranked a “10” into the last position in the array, here is what that would look like:

The player at index 7 in the array needs to move 2 spots to get to index 9, the last element.

So, there are 2 key questions:

  1. How do we move elements through the array?
  2. How do we reorder the elements correctly as they are moving?

As for “moving” elements through the array, we must iterate through the entire array to move elements. We can do this with:

  1. A “for” loop
  2. A “do/while” loop

In this example, I will use a “for” loop. Then, as we are moving elements, we will need to decide how far to move each element within the array.

We can create comparisons via “if” statements. So, every time we move an element in the array, we must use an “if” statement to see if it should be moved (and how far it should be moved)

So, here’s an animated version of how the player with a rating of 10 goes from index 7 to index 9:

  1. When the index is 6, we compare the player at index 6 to index 7. Since 1 < 10, we do not change the order.
  2. When the index is 7, we compare the player at index 7 to index 8. Since 10 > 4, we move the element in index 7 back to index 8.
  3. When the index is 8, we compare the player at index 8 to index 9. Since 10 > 5, we move the element in index 8 back to index 9.

That’s an example of one element that we need to move. Now let’s see how to take this action on every element with bubble sort.

Turning it into an Algorithm

Now we need to think about how to convert this to a scalable algorithm that will work on any array of numbers.

As shown above, we will need to iterate through the array, so let’s start off with a “for” loop. We will create a function called bubbleSort that takes an array as an argument.

let bubbleSort = (arr) => {
  let length = arr.length
  for (let i=0; i < length; i++) {
     // rest of function goes here
  }
}
bubbleSort (players)

There is one important fact that will define the rest of this algorithm: we can only move elements through the array by comparing the element to a single other element in the array.

If it was possible to have some sort of “memory”, we would be able to reorder these elements in one complete iteration through the array. But we do not have any “memory”, so we will need to compare elements one by one.

Here’s what one iteration through the array would look like. We still haven’t written the logic to make it work, that comes next:

There is a big issue: when we get to the end of the array, it is not properly sorted! Only the best player has achieved the highest rank. In the rest of the array, values are still out of order.

In fact, since we can only move elements one by one, we will need to iterate through the array up to the length of the array. In this case, that means we may need to iterate through 10 times! That means we will need nested “for” loops.

Finishing Bubble Sort

Okay, so now we need to add a second “for” loop within the first “for” loop. This is where we need to write the “swapping” logic.

Let’s figure out the swapping logic. We need to compare two elements: the element with the current index. and the next element. So, the element with the current index + 1. If the current element is bigger, we will flip the positions.

The “if” statement is pretty simple:

if (arr[index] > arr[index+1])

But, beyond that, we need to store the current index in a separate variable if the swap is going to happen.

Remember this example? When the player with a “10” rating goes below the other elements, it is being stored in a variable.

Here’s what that code looks like:

if (arr[index] > arr[index+1]){
  let holder = arr[index];
  arr[index] = arr[index+1]
  arr[index+1] = holder;
}

In the GIF above, the holder variable is updated twice since the top-rated moves by two positions.

One last thing before we combine the two code blocks: After every iteration, we are ensuring that the end of the array becomes a queue of the top-rated players. That means we do not need to continue to iterate through those elements, so the number of iterations should shrink each time.

Here’s the final code:

let bubbleSort = (arr) => {
  let length = arr.length
  for (let i=0; i < length; i++) {
    for (let j=0; j < (length-i) - 1; j++) {
      if (arr[index] > arr[index+1]){
        let holder = arr[index];
        arr[index] = arr[index+1]
        arr[index+1] = holder;
      }
    }
  }
}

bubbleSort (players)

In the second “for” loop, we ensure that we use “length-1” for the initial number of iterations, because we know that the last element in the first iteration of that loop will be the highest value.

Here’s an animation:

Get More Tutorials

Did you enjoy this tutorial? Check out the CodeAnalogies blog to get my latest tutorials on web development topics.

Discussion

pic
Editor guide