Hacker News Reader

Comment by zeta0134 | Hacker News Reader

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.

View on HN

Why use it over insertion sort which is faster and easier to implement?

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.

The primary complication is that objects move around between frames, so the list doesn't stay sorted. Insertion requires a second scan once I've found an object that is out of position, whereas bubble can swap right away. (The candidate object is always N-1, after all.)

My goal is to stop working as soon as possible; this is a 1.7 MHz CPU and it has many other tasks to perform on a given frame. It's hard to appreciate unless you sit down to actually do it, but on a processor this slow, the scanning of the list and the comparison of depth is not cheap. It's computed on the fly as we go, there isn't spare RAM to cache it, and it changes every frame anyway. All of that makes the scanning and comparisons way more expensive than the eventual swap.

Insertion would be ideal here for a freshly spawned object, since we already know it is out of position and merely need to find its destination. (The work to shift the rest of the list down isn't super expensive, thankfully.) In practice this is already a big enough visual change that the player doesn't have much time to notice a depth error before it corrects itself.

A time traveler.

Traveling through time at a rate of 1sec per second.

Reply on news.ycombinator.com