# Bubbling Up With Bubble Sorts

### Vaidehi Joshi Sep 23 '17

There seems to be an ongoing joke in the programming community that transcends language, library, or frameworkâââeveryone seems to know that bubble sort is a Bad Ideaâ˘. I remember hearing someone joking about this for the first time years ago; they were ragging on bubble sort, laughing about how it was the worst implementation of a sort algorithm, and how they couldnât understand why anyone would ever useÂ it.

Iâve heard this joke made again and again in the years since, and for awhile, I just accepted it at face value. Sometimes, Iâd even laugh right along with everyone else when they made a bubble sort joke, not knowing why people thought it was so terrible. I usually think that itâs better to make up your own mind about something, rather than just listen to someone elseâs opinions on it and and accept them as gospel. I did this for a long time with bubble sort. But I donât actually think that this was a good practice.

It was only when I started this series that I decided I would put all of that aside. Maybe bubble sort really is a terrible algorithm. Or perhaps itâs just misunderstood, or poorly used. And maybe it can even be made better, and optimized. How would I ever know these things unless I learned about themÂ myself?

So, today weâre going to do exactly that: weâre going to think for ourselves. Itâs time to put an end to all the rumors floating around about bubbleÂ sort.

### Bubbling basics

Before we can really make any fair judgements on the bubble sort algorithm, we need to understand what exactly it *does*, and how it works. A ** bubble sort algorithm** iterates through the list or array that it is given, and compares each pair of adjacent elements in the list by size. If they elements are in the incorrect order, it swaps them, and then moves on to the next pair of elements.

Definitions are a great starting point, but for me, things only really get cemented when I see them in practice. So letâs take a look at what this definition actually means from a pragmatic standpoint. In the example here, we have a collection of unordered numbers that need to be sorted: 9, 7, 4, 1, 2. How would bubble sort handleÂ this?

Well, we know that bubble sort will compare two pairs at a time. Naturally, it will start off comparing the first two elements in our listâââthe first pair. The algorithms looks at the first pair (in this case, 9 and 7), and determines whether the first element is in the correct place. Effectively, itâs just using a > or < operator to do this, depending on how the sort is implemented.

Since 9 is greater than 7, the algorithm knows that it should come after 7. Since these two numbers are in the incorrect order *relative to one another*, it will swap them, which will change the order of just those two elements in the list. Keep in mind that it has no idea if the 9 is the largest number in the listâââit only knows about two numbers at any given point, since an algorithm canât scan a list quickly with its eyes like weÂ can.

Okay, so thatâs how the bubble sort algorithm functions when comparing two elements at a time. But how does it actually sort through the entire list? Letâs look at what the algorithm would do next, using the exact same set of numbers in ourÂ example:

We start off comparing the first two elementsâââ9 and 7âand, since theyâre out of order, we swapÂ them.

Next, we compare the second and third elements: 9 and 4. The number 9 is definitely bigger than 4, so it should come after. This means we have to swap these two elements asÂ well.

The next two elements are 9 and 1. Again, the 9 should come after the 1, and not before, which means we need to swap *again*. Finally, weâre on the last two elements in this iteration: 9 and 2. The number 2 should definitely come before 9, so weâll swap these two elements so that theyâre in the correctÂ order.

Phew! That was just one single iteration of bubble sort. And our list *isnât even sorted yet*. Weâd need to keep repeating this set of actions again and again until the entire collection of elements was sorted. If this was just a *single* iteration, thereâs one big question on my mind now: how many times would we have to iterate in order to sort the entire collection? Imagine if we had a list of 10 or 20, or 50 unsorted elementsâââI really donât want to iterate through each set in order to know how much work itâs going toÂ be!

Instead, letâs try and see if we can find a pattern, and make some abstractions about how many iterations weâd have to make given an array with *n* elements.

We can start off with an easy example. With an unsorted list of just 2 numbers, we need to iterate only once, since in a single pass, we compare the one pair that makes up theÂ list.

For an array of three numbers, we need to iterate twice in order to sort completelyâââthe first iteration, weâd move one number to itâs correct place, and the second iteration would sort the entireÂ list.

I havenât drawn it here, but for an array of four numbers, weâd need to iterate thrice in order to sort it completely. Hopefully these few small examples is helping you see a pattern thatâs emergingÂ here!

In general, given a collection of n unsorted elements, it takes (n-1) iterations through the list in order to sort it using the bubble sort algorithm.

This generalization can be super helpful to us when weâre given large arrays, and we want to know how many times weâll need to iterate through it if we plan on using bubble sort as our sorting algorithm.

### Optimal bubbling

Now that weâve seen one pattern emerge in bubble sort, it should be a little easier to catch a couple of others, too. Thereâs one characteristic of bubble sort thatâs really interestingâââand itâs actually the reason why bubble sort got itâsÂ name!

Letâs look at an example, starting off with an unsortedÂ array:

In this example, each iteration is responsible for moving the largest unsorted element to its correct place in the array. For example, the first iteration effectively moves the largest number, 12, to the end of the list. The second iteration moves the second largest number (or, the largest *unsorted* number), 9, to its correct place in theÂ list.

This is what gives bubble sort its name: the largest numbers begin to âbubble upâ to the end of the list, where theyÂ belong.

Of course, depending on how bubble sort is being implemented, this could also be reversed, so that the smallest numbers are being âbubbled upâ to the front of the list. Regardless, in both cases, the bubbling of numbers comes from the way that bubble sort compares and swaps each pair of elements as it iterates through the collection.

We can also see *another* pattern here, too! Notice how we didnât need to compare the last two elements, 9 and 12, in the second iteration; they were effectively already sorted from our first pass through theÂ array.

Letâs try to generalize this pattern again, and try to find a rule that weÂ follow.

We saw that, after two iterations through our array, checking the last two elements was unnecessary, since they were alreadyÂ sorted.

If we wrote out a third iteration, weâd see that weâd end up with [3, 1, 8, 9, 12] on the third pass, and the last three elements sorted. This means that we wouldnât need to check the last three elements.

You can probably predict what would happen next: on the fourth iteration, the last four elements would be sorted on the second pass. The pattern that weâre seeing here could be summarized into the following rule:

After x iterations, checking the last x elements in a collection is redundant.

This is a good thing to know, because itâs one way that we could optimize bubble sort! If we know that the last *x* elements donât need to be compared, we can break out of an iteration and save ourselves both some time and someÂ memory!

Now that weâve looked at bubble sort very closely, we can being making some larger generalizations about this algorithm.

A handy thing to remember about bubble sort are that a single iteration puts one element (usually the largest unsorted element) in itâs correct place in the array. Itâs also good to keep in mind that it takes *(n-1)* passes through a collection, where *n* is the total number of elements, in order to sort the entireÂ thing.

### How many bubbles is too manyÂ bubbles?

Okay, itâs time for us to talk about the elephant (blowing bubbles) in the room: bubble sortâs inefficiency. I wonât lie to youâââitâs definitely slow and inefficient. But, I donât encourage you to just take my word for it. Instead, letâs figure out *why* itâs slow and inefficient, together!

I think the best way to actually see the speed and efficiency of a bubble sort algorithm is by implementing and then running it. Hereâs my implementation of bubble sort, based on Rosetta Code's JavaScript version, which Iâve modified:

```
function bubbleSort(array) {
var isSorted = false;
while (!isSorted) {
isSorted = true;
// Iterate until we get to the last element
for (var index = 1; index < array.length; index++) {
console.log("comparing " + array[index] + " and " + array[index - 1]);
// If the element to the left is bigger, then swap the element
// that we're currently looking at with its left neighbor.
if (array[index - 1] > array[index]) {
isSorted = false;
console.log("SWAPPING " + array[index] + " and " + array[index - 1]);
// Swap elements by creating a temporary reference.
var temporaryReference = array[index - 1];
array[index - 1] = array[index];
array[index] = temporaryReference;
}
console.log('array is now ', array);
}
console.log(" **one full pass through array**");
console.log("***is array sorted? ", isSorted);
}
return array;
}
```

Iâve added some console.logâs to help us see whatâs actually going on here. If youâre curious, you can run this algorithm yourself, using the JavaScript console on your browser! For our purposes, weâll use the same array we started off with at the beginning of this article: [9, 7, 4, 1,Â 2].

```
var myArray = [9, 7, 4, 1, 2];
bubbleSort(myArray);
```

When we call our bubbleSort function, hereâs what shows up in theÂ console:

```
> comparing 7 and 9
> SWAPPING 7 and 9
> array is now (5) [7, 9, 4, 1, 2]
> comparing 4 and 9
> SWAPPING 4 and 9
> array is now (5) [7, 4, 9, 1, 2]
> comparing 1 and 9
> SWAPPING 1 and 9
> array is now (5) [7, 4, 1, 9, 2]
> comparing 2 and 9
> SWAPPING 2 and 9
> array is now (5) [7, 4, 1, 2, 9]
> **one full pass through array**
> ***is array sorted? false
> comparing 4 and 7
> SWAPPING 4 and 7
> array is now (5) [4, 7, 1, 2, 9]
> comparing 1 and 7
> SWAPPING 1 and 7
> array is now (5) [4, 1, 7, 2, 9]
> comparing 2 and 7
> SWAPPING 2 and 7
> array is now (5) [4, 1, 2, 7, 9]
> comparing 9 and 7
> array is now (5) [4, 1, 2, 7, 9]
> **one full pass through array**
> ***is array sorted? false
> comparing 1 and 4
> SWAPPING 1 and 4
> array is now (5) [1, 4, 2, 7, 9]
> comparing 2 and 4
> SWAPPING 2 and 4
> array is now (5) [1, 2, 4, 7, 9]
> comparing 7 and 4
> array is now (5) [1, 2, 4, 7, 9]
> comparing 9 and 7
> array is now (5) [1, 2, 4, 7, 9]
> **one full pass through array**
> ***is array sorted? false
> comparing 2 and 1
> array is now (5) [1, 2, 4, 7, 9]
> comparing 4 and 2
> array is now (5) [1, 2, 4, 7, 9]
> comparing 7 and 4
> array is now (5) [1, 2, 4, 7, 9]
> comparing 9 and 7
> array is now (5) [1, 2, 4, 7, 9]
> **one full pass through array**
> ***is array sorted? true
>> (5) [1, 2, 4, 7, 9]
```

Wow, that was a *lot*. Letâs take a look at whatâs going on here. We can see that the algorithm is doing exactly what we were doing when we drew out each iterationâââitâs just doing it way faster than us! We can see it comparing two elements at a time. If we look for the instances of **one full pass through array**, we can see what the array looks like at the end of a single iteration. Given the fact that this array only has five elements in it that need to be sorted, there are currently 16 comparisons being made here. That seemsâŚnot great.

This implementation also hasnât been optimized at all: youâll notice that, even after the first iteration, we continue to see this printed out, again and again: comparing 9 and 7. This is a little silly, and thatâs part of what makes bubble sort a slow algorithm; it makes a lot of comparisons, but it doesnât necessarily make them in an intelligent way.

Thereâs another issue, too: what if our list was already sorted? A naive implementation of bubble sort would iterate through the entire list, even if it was sorted, and use a lot of time and memory to doÂ so.

However, there is *one* easy thing that we can do to avoid this crazy repetition of unnecessary work. We can check and see if weâre making any swaps in our first iteration; if weâre not, we know that the list must be sorted, and we can stop iterating.

If we look back at our JavaScript implementation, weâll notice that weâre actually doing exactly that! The isSorted variable is acting as a flag that weâre setting when we start iterating.

```
var isSorted = false;
isSorted = true;
```

If we never end up swapping an element in our first iteration, we know that this array is already sorted. The isSorted flag, which was set to true initially, will never be turned offâââthus, we know that the array is sorted in the very first pass, and we can break out of the loop without doing a bunch of unnecessary iterations.

But evidently, even though weâve added this optimization in our code, itâs still pretty slow and seemingly repetitive.

If bubble sort is bad, we should probably figure out just *how* bad it is. We know that we must make *n* number of iterations through an array of *n* total elements in order to sort it. We also know that, within each iteration, we must check all *n* elements in theÂ array.

Multiplication would tell us that if weâre iterating through all *n* elements, and within each iteration, checking all *n* elements, weâre basically multiplying *n x n*, which isÂ *nÂ˛*.

In the context of time complexity, we could say that the Big O notation of a bubble sort algorithm isÂ ** O(nÂ˛)**.

Based on what we learned in last weekâs post on selection sort, we also know if we have a loop nested within another loop in an algorithm, thatâs a good indicator that the Big O notation of the algorithm will be *quadratic*. That is to say, as our array doubles in size, the amount of time it would take for us to sort through it would *quadruple*.

However, similar to selection sort, bubble sort has a quadratic time complexity, but a *constant* (or, ** O(1)**) space complexity.

Letâs take a look at some of the other ways that bubble sort stacks up to the other algorithms weâve looked at already, using the classifications that weâve already learnedÂ about.

We know that bubble sortâs time complexity is ** quadratic** , or O(nÂ˛), in Big O notation. Bubble sort doesnât require that much additional memory when it runsâââit only needs a few pointers at a time in order to keep reference to the pairs that it is looking at, and maybe swapping (for example, in our code, the temporaryReference variable). Since it only requires O(1) constant space, we can say that it is an

**, which operates directly on the inputtedÂ data.**

*in-place algorithm*Bubble sort is also a ** stable** algorithm, meaning that it preserves the relative order of the elements. If we think about it, this makes sense: imagine an array with two instances of a number: [4, 2, 3, 3]. When comparing the two instances of 3, the algorithm wonât swap them if the one on the left isnât larger than the one on the right. Thus, their relative order would remain theÂ same.

This algorithm is also an ** internal** sort, which means that all the data is stored within the main memory of the computer. This is vital to how bubble sort functions because as the algorithm processes data, it needs all of it to exist in one chunk; if this algorithm were external, it would result in even worse performance than it already has, as it would have to reference chunks of memory that could be potentially stored all over theÂ place.

Finally, we are already sure that bubble sort is both ** non-recursive** (and instead, iterative), and a

**sort, since by definition it iterates through an array and compares two elements at aÂ time.**

*comparison*Based on all of these qualifications, itâs a little easier to see why bubble sort gets a bad rap. Itâs pretty slow, makes a lot of comparisons, and takes a long time. But it is fairly easy algorithm to understand, and it might be useful if you donât care about how much time an algorithm will take, or if you have a very small set of data to sort. However, most of the time, that isnât the case, which means that most of the time, youâll want to avoid bubble sort if youâre thinking about usingÂ it.

Everyone seems to know that bubble sort is generally bad newsâââeven Barack Obama knew that back when he was a senator inÂ 2008:

But guess what? Now you know *why* itâs a bad idea, how to optimize it, and how to talk someone else out of using it. Hopefully, you wonât ever have to do that,Â though!

### Resources

Because bubble sort is such an *infamous* algorithm, thereâs a lot of reading that you can do on it. However, Iâve found videos to be particularly helpful for this algorithm, since they really help illustrate the âbubblingâ that happens. I have included a few good ones in the links below. Happy bubbling!

- The Bubble Sort, Interactive Python
- Sorting algorithms/Bubble sort, RosettaÂ Code
- Algorithms: Bubble Sort, HackerRank
- Bubble sort algorithm, mycodeschool
- Bubble Sort, HarvardÂ CS50

*This post was originally published on medium.com*

This is a really great introduction to algorithm analysis! I never thought bubble sort could be so educational.

Once you've understood this, and want a tad bit more, see The amortized cost of vector insert is 3

I appreciate you identifying ways to optimize Bubble sort, even though it remains inefficient compared to other sorts. You inspired me to code it out: wesleylhandy.github.io/bubble-sort/

Hi Wesley,

This is so cool! Thanks so much for making it. Seeing the benchmarks for the three sort versions is

supercool -- particularly in different browsers :)Great write-up.