Bubble Sort is one of the most widely discussed algorithms, simply because of its lack of efficiency for sorting arrays. If an array is already sorted, Bubble Sort will only pass through the array once (using concept two below), however the worst case scenario is a run time of O(N²), which is extremely inefficient.

Even former President Barack Obama recognizes the inefficiency of Bubble Sort.

When we chart the growth-rate of O(N²), we see that, compared to other sorting algorithms like Merge Sort, which is O(N Log N), it grows at a much quicker scale.

Given the atrocity that is Bubble Sort, it’s still important to understand the algorithm and decipher why it’s so poor.

Let’s delve into two concepts for coding Bubble Sort.

# Concept 1

- Iterate through the array and check each element against the next element in the array.
- If the current element is larger than the next element, swap them.
- If it’s not greater, move the pointers up and compare the next two elements.
- Once we reach the end of the array, we know that the largest element is in the last position.
- Repeat this process N times where N is the length of the array, and each time, iterate up to the last-sorted element.

### Visualizing Concept 1

Let’s take a look at how this would be run on an array of length 6.

### Concept 1 Code

We need to have two pointers (two nested loops) for concept one. Each time we iterate through, the upper bound decreases by one, as we know that this index contains a sorted value.

```
function bubbleSortConcept1(arr) {
for (let j = arr.length - 1; j > 0; j--) {
for (let i = 0; i < j; i++) {
if (arr[i] > arr[i + 1]) {
let temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
}
}
}
}
```

# Concept 2

- Iterate through the array and check each element against the next element in the array.
- If the current element is greater than the next item, swap them.
- Indicate that a swap has taken place.
- If a swap occurred, loop through the array again.
- We know that the array is sorted when no swaps have occurred.

### Concept 2 Code

We only need one pointer with this method, as we’re using a variable to store a Boolean, indicating whether or not a swap occurred. In contrast to concept one, this concept requires us to iterate through each item in the array each time we pass through it.

```
function bubbleSortConcept2(arr) {
let swapped;
do {
swapped = false;
console.log(arr);
arr.forEach((item, index) => {
if (item > arr[index + 1]) {
// Save the value to a variable so we don't lose it
let temp = item;
arr[index] = arr[index + 1];
arr[index + 1] = temp;
swapped = true;
}
})
} while (swapped);
}
```

# Run Time

Bubble Sort is one of the most inefficient sorting algorithms coming in at O(N²). In the worst case scenario, we will have to compare each element against every other element in the array, hence O(N²).

## Discussion

Two years ago on interview I was asked to write bubble sort on a paper. I guess it's the only sorting algorithm I can write without google help 😀

I'm a visual learner, so it's useful for me to visualize an algorihtm process. I created the bubble sort visualization to better grasp the concept.

You can fork and play with it here.

Thanks, Emma for the explanation.

Eugene, I m another visual learner too :) I want to put visualgo.net here. That's super helpful for understanding algorithms.

Yeah, visualgo is a great resource to grasp algorithms by visualizing them step by step.

Horrible interview!

I'm a designer who is learning to code and I found this a little confusing.

I don'tunderstand why you're nesting stuff the way you are in code. How can there be two ways of writing the code if the essential logical idea of the sort is the same?

Why do you callthem pointers? I thought pointers were a thing in c++ for telling a program where stuff was stored in memory?

Also I didn't understand what o(n

^{2)}meant. I'm guessing that as the array length grows, the number of operations required grows exponentially? But why?Hello! You are confused because you never studied Algorithm Analysis or Complexity Analysis. It is basically the study of algorithm performance... this course is the core of a Computer Scientist degree, for example!

1)

How can there be two ways of writing the code if the essential logical idea of the sort is the same?=> When analysing algorithms, you will discover it is common to do the same thing in a lot of different manners. The main idea can be the same, but the way it is executed is different. Both of the versions of this Bubble Sort are looping through the array items a lot of times (more than N times, where N is the number of items in the array). Both of the versions also have the same idea of bubble sort, which is: Comparing pair of elements and swap them in a way that on the end of each loop, the highest element will be in the end of the array. You can discover that by running thebubbleSortConcept2on your browser, by running this:bubbleSortConcept2([5, 4, 3, 2, 1]). It will show you the resulting array after each loop, which is: An array that have the highest element on the end of it. This is the main idea of bubble sort and both algorithms are doing that!2)

Why do you callthem pointers?=> Pointers doesn't exist only inC++orClevel. In fact, most part of the languages (or all of them) use pointers inside. Some veryhigh-levellanguages (Java,Ruby,Python,R, ...) just hide that information to you, but it is using the pointers in the depths, since thesehigh-levellanguages convert the code to alow-levellanguage and they need to deal with pointers!C/C++are considered high-level languages, but in a lower dimension than the ones I just mentioned, sinceC/C++needs to make you deal pointers. I will try to be very succinct:Pointers are just variables that points to another variables. That's it. (In deep therms, it points to amemory addressof another variable, but you can study more of that if you want). Now, let's go to the first sorting example... Theiand thejvariables are pointers, because they points to the position (index) of an element in the array. :) On the second sorting example, theindexis the pointer, for the same reason.3)

Also I didn't understand what o(n2) meant=> Yeah, that is a bit complex to explain to you, as it envolves the core of Algorithm Analysis, haha, but I will try. TheNis the array length, as you noticed. The algorithm loop through the array length more thanNtimes, the question is: Can you figure out how many comparisons (if's) this algorithm will have on the total? This will show the nature of the bubble sort. You can check the quantity of comparisons by adding this`comparisonCount`

here...Here are some results:

As you can see, the quantity of

Comparisonsis growing much more faster than theN (length), this indicates that the order of magnitude of this algorithm is greater thanN, now you need to find the order of magnitude in which theComparisonsis greater than theN (length).You need to find the equation that gives you the quantity of

Comparisonsbased on theN (length). On the bubble sort, this equation is:You can verify it applying to different examples, let's take the last one...

Now, why it is O(n

^{2)}after all of this explanation?`n(n - 1)/2`

is the same as:`(n^2 - n)/2`

.You need to study what is the

O notation/Big O notationto enter on the details, but, in summary, you need to extract the function thatgrows fasteron this equation:`(n^2 - n)/2`

.ngrows faster than^{2}n? Yes! So it isO(n^{2)}Thank you, this was super helpful! Your explanation of how n

^{2}works was in particular useful.This goes back to the principles of computer science, so you might want to read up on those principles if you're confused.

There are many different ways to write code, there's never just one answer.

Pointers are just that; pointers to a spot in an array. They keep track of the index we're at. I could have called them anything as they're just variables.

O(N

^{2)}refers to the run time. Because we're comparing every element with every other element, and Big-O refers to the worst-case scenario or upper-bound, the most comparison's you'll have to do is N * N.Thanks. Reading up on those basics is a big part of what I've been trying to do lately, one reason why I found your article. Thanks!

I was curious as to what sorting algorithm JavaScript uses, and apparently there's no universal specification. Different browsers seem to use different algorithms.

bugzilla.mozilla.org/show_bug.cgi?...

Did you create this content?? It was very clear and right now I am looking for references just like this. Thanks!

Haha yes I created it. Why would I post it if I hadn't? :P

You are right!! What I meant was if all the material was made by you or you got it from a book or something. I'm a visual learner and the way you presented the info was very clear for me.

Ahh yeah haha I see. No I create them all myself using Sketch :)

Super cool Emma!

I want also to point to a bubble sort visualizer built in JavaScript.

codeguppy.com/code.html?visual_sort

I'm sure that this is very good content for the beginners! Good job with this one :) Waiting for the next one.

Loved this ! great explanation emma !!

Thank you but... aaammm... what else. I'm curious if there are some green solutions.

Unfortunately there aren’t any green solutions for sorting an array.

This seems kind of inefficient at first but if you think about it it kind of makes sense. Best case scenario an array is already sorted, which logically still takes N steps since you have to walk through each element of the array to know it’s sorted.

But usually the array won’t be sorted, which means you still have to take N steps, plus even more steps to actually do the work of sorting the array, which is where we get second N in O(N

^{2).}You can do better than N

^{2}by using certain algorithms like merge sort, but even then you’re still limited by the fact that you have to touch every element at least once, plus you have to take extra steps to reorganize the content of the array, and it turns out the most efficient way you can do this is in O(N log N) time.Didn't run/test yet but has the doubt in Concept 2 Code: what about arr[index + 1] when at the last item is coming in the iteration.. will it be array index out bounds ?

What does obama have to do with anything? He also isnt a coder nor dev. JFC stay on topic please

Considering the post's topic is "bubble sort isn't good" and the reference was "even a President who didn't study CS knows bubble sort is good" it sounds perfectly on-topic to me. Using anecdotes to illustrate and highlight ones' points are a basic part of writing good articles, which I should know since I studied journalism for four years.

Thanks Max!

Hey thank you for continuing to make good content like this, despite rude comments like the above one 👍

Not that I need to defend myself to you... but it was to show the fact that everyone is aware of how crappy Bubble Sort is. If you don't like my post, you can leave. I don't want negative people on my blogs.

I hope you get help to fix whatever is so bad in your life that you felt it necessary to comment rudely on someone's blog post.

First: what Emma said.

Second: I don't think one has to be a coder/dev to understand basic computer science as bubble sort (and trust me, that's pretty basic, since I learned it in school when I was 16), nor I think one can't have passion for a specific matter despite working on completely different things.

I also think that mr. Obama totally could have some basic self tought knowledge of CS, giving the fact that he always pushed for CS education for everyone, not only for those who see themselves as the next Steve Jobs.

It is also completely possible that he attended at some CS 101 in his years at Columbia University, that appears to be one of the best in terms of CS teaching, and I'm pretty sure that Bubble Sort was already a thing in the 80s.

I believe that one can have passion about one topic despite working on total different subjects: one can be a dev by day and quilt sewer by night, or be an anatomopathologist that spends all his friday nights in karaoke bars just because likes to sing. Or be the POTUS and still have read one or two books about computer science, why not?

Last but not least: I wouldn't call Emma's reference "off topic", being one and a half line of text in an article that doesn't like to be a medium length tweet...

One last piece of granny advice: if you can't say it nicely, don't say it at all.

Cheers

You snowflakes sure read a LOT in to what he asked. "WHAT DOES OBAMA HAVE TO DO WITH IT?" which is NOTHING. You guys got all bent out of shape, creatively bashing him and claiming he has something wrong with his life...wow. No wonder young people (especially girls) are scared off of coding. There's less trash talk in Call of Duty in an under-15 match.

Dude, no one is taking CS advice from Obama. It was a joke. Don't find it funny? Move on. No need to rain on others' parades.

Thanks Yechiel! :)

JFC? Grow up. She stayed on-topic the entire time. Keep rude comments like this one to yourself.

Thanks for the great blog post, Emma!

REEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEE

Thanks Justin!