If you know one thing about bubble sort, it’s that it’s a horrible sorting algorithm. But Bubble sort is great for one thing. Bubble sort has one good use case: Beer tasting. Let me explain:
Here follows the full video transcript:
If you know one thing about bubble sort, it’s that it’s a horrible sorting algorithm. It famously has an O(n^2) time complexity, that is, if you want to sort n things, you need to make, on the order of, n squared comparisons. And that’s not… great.
But Bubble sort is great for one thing. Bubble sort has one good use: Beer tasting.
As you surely know, there are two main goals when having a beer tasting.
- You want to have all the beers sorted from worst to best.
- You want to have drunk all the beers.
It’s especially for goal (2) where algorithms like quick sort or heap sort won’t cut it, as they are too efficient. The beers get sorted, but the beers don’t get drunk. Two other nice properties with bubble sort are also that
- It sorts the beer “in place”, which means you won’t need to move the beers all over the table, and you’ll have plenty of space for a snack bowl.
- It is resilient to an unreliable comparison function. If the comparison function starts becoming a bit too drunk, and makes mistakes, or decides, in the middle, that it actually doesn’t really like IPAs, then, with Bubble sort, you’ll still end up with a kinda sorted list of beers.
So, if you don’t remember exactly how bubble sort works, or you just want to learn the correct ordering of this selection of industrial lagers, here’s the Bubble sort algorithm applied to beer tasting. We’ll start at the beginning of the list, comparing the two first beers.
[compares the two first beers]
If we believe they are in the right order, with the best one to the right, we do nothing. However, that would make Budweiser the tastier beer, and yeah… that’s not the case. As they are in the wrong order, we’ll instead let Budweiser and Staropramen switch places. We’ll then move one step, and try the next pair.
[compares beer two and three]
And, god, this is a hard one. But I think, today, Pilsner Urquell will win out. So they are in the correct order, and we do nothing, and move one step.
[continues comparing the rest of the beers]
And now we continue comparing, maybe switching, and moving a step, all the way to the end of the list. At this point, we’ve taken a pass through the whole list, and now we ask ourselves the question: Did any of the beers switch places? If no, the list is sorted, and there is nothing more to do. But lucky for us, we switched quite a lot, so we can keep on drink… tasting beer. You also saw that Pilsner Urquell kinda “bubbled” to the top of the list. That’s why it’s called bubble sort, the top items will “bubble” to the top. It has nothing to do with the carbonation, this algorithm works well for wine tasting, as well.
Alright! Let’s take another pass!
[takes another pass through the list of beers]
And now Staropramen has bubbled to second place.
One more pass!
[takes another pass]
One more!
[A last pass, with no switches]
Aha! So in this last pass, we didn’t make any switches, which means the beers are now sorted from worst to best and, as bubble sort is such an inefficient algorithm, the beers are now also mostly finished.
That’s why the one good use of bubble sort is beer tasting!
Or wine tasting. Or I guess, tea tasting. Should work for non-liquids as well. Cheese tasting, maybe?