8 Mins to Master BubbleSort
Hi! Today is all about BubbleSort. In the next 8 mins, you will nail 5 things: why this name, how it works, and its implementation, followed by a discussion on its time complexity and optimization. Without further ado, let’s get started.
Why this name
BubbleSort is a sorting algorithm. It gets this name because elements tend to move up into the correct order like bubbles rising to the surface. Let’s see how it works with an example.
How it works
Here is an array: [2,7,4,2]. The problem is to sort the array in non-decreasing order using bubblesort. So in the end it should be like this: [2,2,4,7].
When playing games, we need rules. It’s the same here. So let me show you the rule:
The idea is to compare the adjacent two elements. The larger one goes to the right.
Ok let’s practice:
[5,3] — the one on the left > the one on the right, so they should swap their position.
[2.5, 3] — the one on the left < the one on the right, so we do nothing.
[3, 3] — the one on the left = one on the right, so we do nothing.
Let’s start the game!
We start our 1st scan with the comparison of the two elements on the very left: 2 and 7. A yellow rectangular is drawn to show what we are comparing right now. 2 is smaller than 7, so we do nothing.
Now we move the rectangular one step to the right, and compare 7 with 4. 7 is larger than 4, so 7 should go to the right. We swap their position.
Again we move the rectangular one step to the right, and compare 7 with 2. 7 is larger than 2, so 7 should go to the right. Time to swap their position.
Up to now, we finished our 1st scan through the whole array. What happened is by swapping the positions, the largest element, 7, is already in its right position. From now on we don’t need to consider 7 anymore.
Let’s start our 2nd scan by comparing the two elements on the very left: 2 and 4. 2 is smaller than 4, so we do nothing.
Now move the rectangular one step to the right, and compare 4 with 2. 4 is larger than 2, so it should go to the right. We swap their position.
Now the rectangular reached the dashed line, which indicates our 2nd scan is finished. As we can see, 4 is in it’s right position now.
Let’s start our 3rd scan by comparing the two elements on the very left: 2 and 2. 2 equals 2, so we do nothing.
What’s more, as the rectangular reached the dashed line, the 3rd scan is finished. After this scan, 2 is in its right position.
There’s only one element left before the dashed line, and nothing to compare with, so we can say this element is in its right position.
Ok, the whole array is now in a non-decreasing order. And the above process is how bubblesort works. It’s always a good idea to draw and visualize the process of the algorithm, before the actual implementation.
Now let’s talk about how to implement BubbleSort. Let’s recall our example.
In the 1st scan of the array, we need to do 3 times of comparisons, which equals the (arrayLength N -1).
In the 2nd scan, we need to do 2 times of comparisons, which equals the (arrayLength N -2).
In the 3rd scan, we only need to do 1 comparison, which equals the (arrayLength N -3).
Pseudo code of BubbleSort:
So now we can write the pseudo code of BubbleSort:
“N” is the length of the input array.
“K” means how many comparisons we need to do in each scan of the array. It starts with (N-1), and ends with 1. Each scan has 1 less comparison than the previous scan, because there’s one more element already in its right position.
“i” means the position of the two adjacent elements we are comparing. it starts with 0, and ends with (k-1), so that it ensures the comparison starts from the very left of the array, and in total there are k times of comparisons in the current scan.
In each comparison, if the one on the left is larger than the one on the right, then they swap their position. Otherwise, we do nothing.
Now that we understand the pseudo code, let’s translate it into real code. It doesn’t matter what language you are using, because the logic stays the same. We’ll use python as an example, and here’s the code:
Python Code for BubbleSort:
Please note that for this code, the input array type is a list of real number, and since BubbleSort is an in-place algorithm, we don’t need to return anything.
I hope you find my walk-through helpful, and made the code easier to understand.
So far we’ve covered what BubbleSort is, and how to implement it, let’s discuss its time complexity and optimization.
There are three types of time complexity: best-case, worst-case, and average. For a short answer, I listed them all for BubbleSort:
Today we’ll go through worst-case time complexity, because it’s most useful.
Worst-case time complexity calculation:
The input array length is N. In the 1st scan, we do a total number of (N-1) times of comparisons in the worst case. In the 2nd scan, we do (N-2) times of comparisons in the worst case. So on and so forth, until in the final scan, we do only 1 comparison.
Please note that after each scan, we do 1 less comparison, because there’s one more element already in it’s right position.
To get the time complexity in the worst case, we calculate how many comparisons we need to do in total, in the worst case. So we sum up the number of comparisons for each scan:
And the sum is like this: (N-1)+(N-2)+(N-3)+…+1. Since it’s an arithmetic sequence, the sum is like this: (N*N/2–N/2) . When N approaches positive infinity, compared to N*N, the rest is neglectable. So the worst case time complexity is O(N2).
One way is to reduce the number of scans:
With the previous method, we need a total of (N-1) scans. Instead, we can set a new stop condition: if not a single element changed its position after this scan, the sorting is finished. It makes sense if you think about this example:
[7,2,2,2,2,2,2,2,2,2]. The array length is 10. Instead of 9 scans, We only need 2.
Another way is to bubble from both ends:
In a single scan, the larger element bubbles to the right, and the smaller element bubbles to the left.
But note that all these improvements won’t work in the worst case scenario, say, this one: [7,6,5,4,3,2,1]. However there are many other sorting algorithms way faster than BubbleSort, such as MergeSort, or HeapSort, which we will discuss in the coming articles.
Thanks for reading! By now, you officially became a master of BubbleSort! YAY!!!~~
Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!
— — Oh, don’t forget to checkout “The Sparkling Pointer” YouTube video on this one!