←back to thread

When would you ever want bubblesort? (2023)

(buttondown.com)
108 points atan2 | 1 comments | 10 Dec 25 21:45 UTC | HN request time: 0.201s | source
Show context
zeta0134 ◴[10 Dec 25 22:49 UTC] No.46225102[source]▶
I used bubblesort on purpose in a game project. Specifically, to sort sprites in an NES game back to front, lazily, spending as few CPU cycles as possible. Bubblesort on the very small list (a dozen objects max), and early exit after the first swap. It eventually completes, and that was just fine. It's tiny, incredibly simple, and somewhat resilient to the list changing from frame to frame as objects spawn and despawn. Each partial sort makes some progress no matter what.

A few other algorithms would have fit the bill just as well, but bubblesort is perfectly adequate, so that's what will likely ship. More complex algorithms end up losing out due to greater initial overhead or larger ROM size.

replies(2): >>46225965 #>>46226389 #
jeltz ◴[11 Dec 25 01:09 UTC] No.46226389[source]▶
Why use it over insertion sort which is faster and easier to implement?
replies(2): >>46227087 #>>46228674 #
1. GuB-42 ◴[11 Dec 25 02:50 UTC] No.46227087[source]▶
There is "early exit after the first swap", which actually makes his algorithm closer to insertion sort than bubble sort. If the list couldn't change between each pass, it would be a very inefficient insertion sort in O(n^3) as you are constantly scanning the part of the list that is already sorted.

But this is a case where theory doesn't count as much as having an acceptable result. It is typical in video games, if it plays well and looks fine, who cares if it is incorrect. Here I guess that sometimes a sprite appears on top of another sprite when it should have been behind it, because of the early exit, but while playing, it turned out not to be noticeable enough to change the algorithm.