Bubble Sort in Action

Let’s walk through a complete example of Bubble Sort.

Assume we want to sort the array [4, 2, 7, 1, 3]. It’s currently out of order, and we want to produce an array that contains the same values in ascending order.

Let’s begin the first pass-through:

This is our starting array:

Step 1: First, we compare the 4 and the 2:

Step 2: They’re out of order, so we swap them:

Step 3: Next, we compare the 4 and the 7:

They’re in the correct order, so we don’t need to perform a swap.

Step 4: We now compare the 7 and the 1:

Step 5: They’re out of order, so we swap them:

Step 6: We compare the 7 and the 3:

Step 7: They’re out of order, so we swap them:

We now know for a fact that the 7 is in its correct position within the array because we kept moving it along to the right until it reached its proper place. The previous diagram has little lines surrounding the 7 to indicate that the 7 is officially in its correct position.

This is actually the reason why this algorithm is called Bubble Sort: in each pass-through, the highest unsorted value “bubbles” up to its correct position.

Because we made at least one swap during this pass-through, we need to conduct another pass-through.

We begin the second pass-through:

Step 8: We compare the 2 and the 4:

They’re in the correct order, so we can move on.

Step 9: We compare the 4 and the 1:

Step 10: They’re out of order, so we swap them:

Step 11: We compare the 4 and the 3:

Step 12: They’re out of order, so we swap them:

We don’t have to compare the 4 and the 7 because we know that the 7 is already in its correct position from the previous pass-through. And now we also know that the 4 has bubbled up to its correct position as well. This concludes our second pass-through.

Because we made at least one swap during this pass-through, we need to conduct another pass-through.

We begin the third pass-through:

Step 13: We compare the 2 and the 1:

Step 14: They’re out of order, so we swap them:

Step 15: We compare the 2 and the 3:

They’re in the correct order, so we don’t need to swap them.

We now know that the 3 has bubbled up to its correct spot:

Since we made at least one swap during this pass-through, we need to perform another one.

And so begins the fourth pass-through:

Step 16: We compare the 1 and the 2:

Because they’re in order, we don’t need to swap. We can end this pass-through, since all the remaining values are already correctly sorted.

Now that we’ve made a pass-through that didn’t require any swaps, we know that our array is completely sorted:

Code Implementation: Bubble Sort

Here’s an implementation of Bubble Sort in Python:

To use this function, we can pass an unsorted array to it, like so:

This function will then return the sorted array.

Let’s break the function down line by line to see how it works. I’ll explain each line by first providing the explanation, followed by the line of code itself.

The first thing we do is create a variable called unsorted_until_index. This keeps track of the rightmost index of the array that has not yet been sorted. When we first start the algorithm, the array is completely unsorted, so we initialize this variable to be the final index in the array:

We also create a variable called sorted that will keep track of whether the array is fully sorted. Of course, when our code first runs, it isn’t, so we set it to False:

We begin a while loop that continues to run as long as the array is not sorted. Each round of this loop represents a pass-through of the array:

Next, we preliminarily establish sorted to be True:

The approach here is that in each pass-through, we’ll assume the array is sorted until we encounter a swap, in which case we’ll change the variable back to False. If we get through an entire pass-through without having to make any swaps, sorted will remain True, and we’ll know that the array is completely sorted.

Within the while loop, we begin a for loop in which we point to each pair of values in the array. We use the variable i as our first pointer, and it starts from the beginning of the array and goes until the index that hasn’t yet been sorted:

Within this loop, we compare each pair of adjacent values and swap those values if they’re out of order. We also change sorted to False if we have to make a swap:

At the end of each pass-through, we know that the value we bubbled up all the way to the right is now in its correct position. Because of this, we decrement the unsorted_until_index by 1, since the index it was already pointing to is now sorted:

The while loop ends once sorted is True, meaning the array is completely sorted. Once this is the case, we return the sorted array: