All About Bubblesort

by kirupa   |   14 December 2014

When it comes to sorting stuff, one of the worst algorithms you can use is known affectionately as bubblesort. It is sooo terrible, that people have stopped naming kids after it. Despite its terribleness, it is important for you to learn how bubble sort works. The main reason is to understand what it does and...avoid doing anything in your code that even remotely resembles it. The other reason is purely for trivial purposes. You'll never know when Alex Trebek belts this out as a Final Jeopardy answer one day.

Anyway, let's get started!

How Bubble Sort Works

Let's say you have a collection of numbers that are currently unsorted:

unsorted numbers

The way bubblesort works is pretty simple. It starts at the beginning and slowly moves through each number until it hits the end. At each number, it compares the size of the number it is at with the number directly next to it. That probably makes little sense, so take a look at the following diagram:

 

adjacent numbers

The first two numbers are compared. Then the next two numbers are compared. Then the next two, and the next two, and so on. You get the picture. The comparison it performs is to see if the first number is smaller than the second number. If the first number happens to be bigger, then the first and second numbers are swapped. Let's walk through this briefly.

In our example, the first comparison will be between the 6 and the 2:

comparison of numbers

The first number is not smaller than the second one - ie, 6 is not less than 2. What you do in this situation is swap the numbers so that your first number is always smaller than the second number:

numbers swapped

Yay! You just completed one step as a human being roleplaying as bubblesort. Next, you move one number to the right and compare the new two numbers that you are standing in front of:

more swapping

The 6 is not less than 0, so another swap takes place:

it's swappin' time!

You repeat this process of sliding over by one, comparing the two numbers in front of you, and swapping them if you need to until you have no more numbers left:

numbers swapped

When you reach the last number, you go back to the beginning and repeat this whole process again. This is because, as you can see, your numbers are still not fully sorted. You repeat this painfully time-consuming process over and over and over again until you get to the point where all of your numbers are sorted perfectly:

the sorted numbers

From bubblesort's point of view, your numbers are considered to be perfectly sorted when you make a pass through your numbers without having to swap any of them around. To put it differently, it means that every two consecutive numbers you looked at were properly arranged from small to large.

Walkthrough

In the previous section, you learned a bit about how bubblesort works. In this section, let's fully clarify everything you've seen so far by doing a full walkthrough. To avoid boring you to tears, I'm going to trim our above example to only four numbers:

trimmed list of numbers

Don't worry. Since we are dealing with bubblesort, these four numbers itself will ensure you do a lot of scrolling (or page turning or hand gesturing) to get to the fully sorted version of things. You've already sorta (ha!) seen the first few numbers, but we'll go through them again with a little more detail for the sake of completeness.

The first run of bubblesort through our four numbers looks as follows:

the first run

 

Now, we start at the beginning and do our old song and dance again:

second round

At this point, if you look at the results of the last step, our numbers are fully sorted. To us humans, we would call it a night and take a break. Bubblesort doesn't know that the numbers are sorted just yet. It needs to run through the numbers one more time to realize that when no swaps take place:

the last run

When no swaps happen, it means that every number is properly arranged. That signals to bubblesort to stop bothering these poor numbers and to go home.

The Code

Now that you've seen how bubblesort operates, let's take a look at one implementation of it:

function bubbleSort(input) {
  var swapSignal = true;

  while (swapSignal) {
    swapSignal = false;

    for (var i = 0; i < input.length - 1; i++) {

      if (input[i] > input[i + 1]) {

        var temp = input[i];
        input[i] = input[i + 1];
        input[i + 1] = temp;

        swapSignal = true;
      }
    }
  }
}

var myData = [6, 2, 0, 9, 1, 7, 4, 4, 8, 5, 3];
bubbleSort(myData);

alert(myData);

If you walk through this code, everything you see should map to what we looked at in the previous sections. The main thing to call out is the swapSignal variable that I use to indicate whether bubblesort has gone through these numbers without swapping any values. Besides that one thing of note, everything else is just simple array and for loop tomfoolery.

Conclusion

As you've seen from the walkthrough, bubblesort is not very efficient. For sorting four numbers, it took about 18 steps if you count the shifting and comparison as two individual operations. This was despite several numbers requiring no further sorting.

Bubblesort is fastest when you are already dealing with a fully sorted list of numbers. It goes through the numbers once, realizes that no numbers were swapped, and then heads over to the local discotheque and does some...discotheque-ing with all of the other cool kids. If you are dealing with a list of numbers that are sorted in reverse, bubblesort takes the longest amount of time. Every single number needs to be swapped and moved over to the end. I feel bad for whatever computing device has to deal with that reversed situation.

Before we call it a night (and join bubblesort at the local discotheque ourselves), below is a table comparing various popular sorting algorithms and their various performance and memory characteristics:

Name Best Average Worst Memory
Quicksort n log n n log n n2 log n (average)
Mergesort n log n n log n n log n n (worst case)
Heapsort n log n n log n n log n 1
Tinsort n n log n n log n n
Bubble sort n n2 n2 1
Selection sort n2 n2 n2 1
Insertion sort n n2 n2 1

You can find a more detailed comparison of these sorting algorithms as well as many others over on the Wikipedia section fully dedicated to this.

And with that, you are free to go and use your newfound knowledge to sort all sorts of things really REALLY slowly. If you want to learn about a fast sorting algorithm that leaves bubblesort behind in the dust, you really should become friends with quicksort.

Getting Help

If you have questions, need some assistance on this topic, or just want to chat - post in the comments below or drop by our friendly forums (where you have a lot more formatting options) and post your question. There are a lot of knowledgeable and witty people who would be happy to help you out

Share

Did you enjoy reading this and found it useful? If so, please share it with your friends:

If you didn't like it, I always like to hear how I can do better next time. Please feel free to contact me directly via e-mail, facebook, or twitter.

Brought to you by...

Kirupa Chinnathambi
I like to talk a lot - A WHOLE LOT. When I'm not talking, I've been known to write the occasional English word. You can learn more about me by going here.

Add Your Comment (or post on the Forums)

blog comments powered by Disqus
Awesome and high-performance web hosting!
BACK TO TOP
new books - yay!!!