## Bubble Sort

by Mirabelle Jones Let’s kick things off with our sorting algorithms by having a look at bubble sort (and not just because it has a cute name)! Bubble sort is a very simple sorting algorithm where we move through each item in an array (group of numbers) and compare two items at a time to see which is bigger. If the item on the right is bigger than the item on the left, we switch them! We continue to do this for the whole array. In this way the largest value “bubbles” to the top by moving to the right as shown.

## Scenario

So what would a bubble sort look like in real life? Well, let’s say you own a Matryoshka (Russian nesting dolls) shop where your display looks like so:

You want to sort the dolls in order of height in order to build a neat new display for them. To do so, you might start by picking up the first doll and comparing it to the one on the right. Is it shorter or taller? If the one on the right is shorter, you might swap them. Otherwise you might leave it where it is, then move on to the next, and compare it. This can be visualized like so (only replace stick figures with cute Russian nesting dolls):

In pseudocode, our sort might look like this:

``````function bubbleSort(allDolls){
var noSwaps = true;
for(i = numberOfDolls; i > 0; i--){
noSwaps = true;
for(var j = 0; j < i - 1; j++){
if(allDolls[j] > allDolls[j+1]){
var temp = allDolls[j];
allDolls[j] = allDolls[j+1];
allDolls[j+1] = temp;
noSwaps = false;
}
}
if(noSwaps) break;
}
return allDolls;
}

bubbleSort([6,3,1,6,4,5,6,9]);``````

This might seem a little complex, but let’s go through it step by step and figure out the logic.

We begin by creating our function and storing the information it needs as a parameter. In this case, we need to know what we’re sorting! So we feed the function a list of our dolls’ heights like so as “allDolls”:

``function bubbleSort(allDolls){``

We’re going to need a way to keep track of whether or not any swaps are left, so we create the following true or false variable:

``var noSwaps;``

Then we want to start the process of comparing the dolls, working our way through the display. We need to have a way of keeping track of the last doll we’re comparing, so we call this doll “i.” To begin with, we set it equal to the number of dolls we have. But the next time through the loop, we’ll know that our last doll is sorted. So we don’t need to sort it again. That’s why we have “i–” which is the same thing as saying “i = i – 1” or: “Hey, decrease i by one!” So each time, the window of items we’re sorting narrows by 1. We want to continue our doll comparison until the last doll we’re comparing is right next to the first doll (doll 0!), hence the i > 0.

``for(i = numberOfDolls; i > 0; i--){``

In practice, this means that if we have 45 dolls, the next time through our loop, we’ll compare up to the 44th doll. And then the next time after that, we’ll compare up to the 43rd doll with all of the dolls, and so on. If we didn’t do this, we’d always keep (redundantly) comparing unsorted dolls with the ones we’ve already sorted!

Inside of this loop, we want to make sure we’ve reset our “no swaps” status to true. This is a bit confusing. Why are we setting this to true if we don’t know if there are any swaps left yet? Well in this case, we’re deciding “no swaps left” is true until proven not true. We want to assume it’s true so we can end our swapping if it isn’t true. And we can’t tell if it’s false until we compare! If this still seems confusing, read on and hopefully it will make sense by the end.

``noSwaps = true;``

Now we enter a loop within a loop (cue inception soundtrack 0 _ 0). This sounds complicated, but let’s remember what we’re doing: we’re comparing every doll with the one to the right to see if it’s shorter or taller, then swapping if necessary. So this means we need to do this for every doll in our display up until the last doll we haven’t sorted, right? That means one for loop where we check every doll against the one to the right WITHIN our loop of counting down (so we decrease our “unsorted dolls” window). So a loop within a loop makes sense here. Our inner loop opens like so:

``for(var j = 0; j < i - 1; j++){``

The comparison happens here where we compare our doll in hand with the one on the right (j + 1) to see which one’s shorter.

``if(allDolls[j] > allDolls[j+1]){``

If the one in hand is bigger than the one on the right, we want to swap them. How do we do this? Well, we have to pull one doll out of its place which creates a temporary place. You can think of this as a placeholder so we know where our doll will go. We’ll call this “temp”. Then we want to move the doll on the right into that space. Finally, we move our doll in hand into the spot marked by our placeholder. Because we swapped, we’ll set “noswaps” to false:

`````` var temp = allDolls[j];
allDolls[j] = allDolls[j+1];
allDolls[j+1] = temp;
noSwaps = false;        ``````

But what if the doll wasn’t bigger? Well, we exit our loop and go back to our outer loop. We decrease our sorting window by knocking one off the end. Then we repeat the inner loop by comparing our dolls. When we’ve reached the end, meaning we have no more comparisons we get to:

`` if(noSwaps) break;  }  return allDolls;``

This means that there are no swaps left! We exit our loops (both of them!) and return our sorted array allDolls.

If you’d like to learn more about bubble sort including how to implement it in real code, check out the sections below.

## Big O Complexity

Best Case: O(n)

Example: our dolls are nearly sorted! This means we don’t have to do much swapping and so bubble sort is not too bad in this case!

Worst Case: O(n)^2

Example: our dolls are in random order or pretty mixed in terms of size.

## Pseudocode

``````1. Start looping at the number at the end of the array. We'll call this number i. We'll loop towards the beginning of the array.
2. Start an inner loop with variable j that goes from the beginning of the array (our list of numbers) to i - 1.
3. If the number at j in our array is greater than the number at j + 1, swap them!
4. Once we're done swapping and no swaps are left, return the sorted array!``````

## Code Examples

Javascript

``````function bubbleSort(arr){
var noSwapsLeft;
for(var i = arr.length; i > 0; i--){
noSwapsLeft = true;
for(var j = 0; j < i - 1; j++){
if(arr[j] > arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
noSwapsLeft = false;
}
}
if(noSwapsLeft) break;
}
return arr;
}

bubbleSort([8,1,2,3,4,5,6,7]);``````

## Sample Problems

Come back soon for these!