# 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.