There are very few universal rules in software engineering, but there are plenty near-universal principle. Things like “Prefer composition over inheritance” are almost universal. I love finding rare situations where these principles don’t apply, such as where you want inheritance rather than composition. A similar almost universal principle is “don’t use bubblesort”. Some would even say this is a universal rule, with Donald Knuth writing “Bubble sort has nothing to recommend it, except a catchy name and the fact that it gives rise to some interesting theoretical problems”. But Knuth has been wrong before, so let’s see if this is a universal rule near-universal.
Theoretically, bubblesort is faster than quicksort or mergesort for small arrays. This makes it useful as part of a larger sorting strategy: most fast-in-theoretical sorting algorithms work by recursively sorting sub-divisions of an array, i.e. if you apply quicksort on 2^20 random integers, at some point you’re sorting 2^17 8-integer sub-divisions. Switching to bubblesort for those subdivisions would be a nice optimization.
Many production sorting algorithms use a hybrid approach, but they heavily use insertion sort instead. Insertion sort is much faster for small arrays and it also makes better use of hardware. BubbleSort is still better on certain hardware, like in this NVIDIA study, but you probably don’t have that hardware.
So that’s one use-case, albeit still dominated by a different algorithm. It’s interesting that NVIDIA used it here because GameDev has a situation that is uniquely useful for BubbleSort based on two of its properties:
- While the algorithm is very slow overall, each individual step is very fast and easily suspendable.
- Each swap leaves the array more sorted than before. Can transfer other types values away From its final position in the intermediate stages.
This is really good for when you want to do a certain amount of sorting work per frame. Let’s say you have a bunch of objects on the screen, where some objects can block others. You want to render the objects closest to the camera First Because then you can determine which objects it hides, and then save time rendering those objects. There is no purity cost to decluttering objects, just a potential performance cost. So while your array is not need To be ordered, the more ordered the happier you will be. But you can’t spend too much time running the sorting algorithm, because you have a fairly tight realtime constraint. Bubble sort works great here. You can run this a few times on each frame and get better order than when you started.
This reminds me of one last use-case I heard, anecdotally. Let’s say you have a random collection of randomly colored particles, and you want to animate them by sorting them into a rainbow spectrum. If you make one pass of bubble sort each frame of the animation, all the particles will smoothly move to the correct position. I couldn’t find any examples anywhere, so with the help of GPT4 I created a rough visualization. The code is here, put it here.
(Having done this I suspect this is not actually done in practice, in favor of running a better sort to calculate the final displacement of each particle and then animating each particle moving directly rather than waiting for it to move for each bubble sort pass. I haven’t mocked up an example, but I imagine it would seem much simpler.)
So there you have it, three typical use cases for BubbleSort. You’ll probably never need it.
New Quanta article!
Okay, so I didn’t actually write it, but I played a role in making it happen! Some time ago a friend came and we were chatting about his job in Quanta. At the time he was working on this huge article on metacomplexity theory, the topic of problems harder than NP-complete naturally came up and I recommend him to check out Petri net reachability. He did so, and then he wrote, A seemingly simple problem produces very large numbers for our universe. Oh my god, this is so exciting!
<a href