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!
Let's say you have a collection of numbers that are currently unsorted:
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:
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:
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:
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:
The 6 is not less than 0, so another swap takes place:
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:
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:
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.
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:
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:
Now, we start at the beginning and do our old song and dance again:
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:
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.
Now that you've seen how bubblesort operates, let's take a look at one implementation of it:
function bubbleSort(input) {
let swapSignal = true;
while (swapSignal) {
swapSignal = false;
for (let i = 0; i < input.length - 1; i++) {
if (input[i] > input[i + 1]) {
let temp = input[i];
input[i] = input[i + 1];
input[i + 1] = temp;
swapSignal = true;
}
}
}
}
let myData = [6, 2, 0, 9, 1, 7, 4, 4, 8, 5, 3];
bubbleSort(myData);
console.log(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.
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.
Just a final word before we wrap up. If you have a question and/or want to be part of a friendly, collaborative community of over 220k other developers like yourself, post on the forums for a quick response!