The Vindication of Bubble Sort
As long-time readers know, I have a strong adversion toward bubble sort. I will loudly argue that there are no valid reasons to teach bubble sort.
Sometimes it’s the case that algorithms have different strengths, and are best at different use-cases. I’d argue that bubble sort is best at no single use case. It’s not fastest, it’s not memory efficient, it is not conservative in terms of writes or reads, and it is not even intuitive, or easy to understand.
If people were taught a different sorting algorithm, they’d never have a need to learn bubble sort, I’d argue. Bubble sort is this kind of weird unintuitive mess we teach for no good reason, and then people remember it precisely because the central mechanism is so weird. Keep swapping adjacent elements until sorted? That’s such an odd way to sort things that it sticks.
I wouldn’t argue all this unless I had an alternative, right? Of course.
Insertion sort is the sort to rule them all. I know it’s not the fastest, or most conservative in terms of writes, or most memory efficient.
But it’s so easy even a child can invent it. And they do.
And for being so simple, it’s still reasonably efficient.
So I thought I were on firm ground, stating there are no use cases for bubble sort. However, last week a friend of mine pointed out they had found one.
When to Bubble Sort
Their problem was this: they wanted a sequence sorted for performance reasons, but it wasn’t critical for functionality. They also could not sort the sequence up-front for two reasons:
- This was a soft-realtime application, so at all points in time, sorting the entire sequence would be too costly and blow several timeouts.
- The sequence itself changed and was replaced every now and then, so in the worst case, even if one spent the cycles sorting it, it could very well be thrown out the next thing that happens.
So my friend – I assume – started thinking of ways of partially sorting the sequence, a little a time. The issue with this if you do it with conventional algorithms is that you’ll have to keep track of how much you have sorted between partial sortings, which can get tricky; doubly so if the sequence is modified between two partial sortings.
Unless you use bubble sort. The central part of the bubble sort is stateless and idempotent on a sorted sequence, but on an unsorted sequence it will always decrease its entropy.
This became a perfect fit in the application in question, since it needed to iterate the sequence every so often anyway, so that iteration could be integrated with the central bubble sort iteration.
In practise, what my friend figured out was a virtually cost-free way to approach a sorted sequence, using bubble sort. I’m extremely impressed.11 The sarcastic cynic in me will still claim that, “Oh, so this great use you found for bubble sort is when you don’t actually need the result to be sorted? Such a good sorting algorithm that is!” but obviously, this is a joke. I’m somewhat blown away by the concept, still.