💾 Archived View for thrig.me › blog › 2024 › 03 › 10 › sort-fail.gmi captured on 2024-07-09 at 01:18:44. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-03-21)
-=-=-=-=-=-=-
So about midways through writing some code, I wanted to display a high scores list sorted in an unusual way, by the absolute value, so that a score of -42 would appear next to that of 42. All very silly. What was not silly was that qsort(3) failed at this task: no idea why, no time to debug what had gone sideways. Probably some tricky thing in the *compar callback function (or not very tricky, if you've been working too much so therefore your error rate is high).
If one assumes that the scores file is already sorted (it should be, or is empty, or has been corrupted and probably should be thrown out) one can append the latest score to the list of scores, then use insertion sort to put the new record where it needs to go. Or use bubble sort, which is more complicated than an insert, but not by much. Or binary search for where the new score needs to go, but it would have taken me longer to find code for that, and then you may have to shift displaced records.
But aren't bubble and such algorithms old and slow and terrible? Yes! But there's only something like 10 or 20 high scores, and the high scores code is not called much, if at all. So it can make sense to go with something simple and robust. When something complicated goes sideways, you may not have the time, inclination, or talent to figure out what has gone awry. The insertion sort took only eight lines of C mostly copied from some 2014 practice code, involved no fancy callback functions, and unlike the qsort code was working in a reasonable amount of programmer time.
A case can be made for more robust code:
"Beyond efficiency". David H. Ackley. 2013.
P.S. Another library, libtcod, also failed horribly and had to be torn out and replaced with bespoke (but working, and debuggable) pathfinding code.
P.P.S. In hindsight, sqlite might be good for high scores, though is a bit more complicated than reading and writing structs with a file descriptor, has some locking gotchas I would probably screw up under time pressure, and I'm not up to speed on using sqlite from C, especially not when in a hurry. Probably one should have tested libraries for these sorts of things.
P.P.P.S. A copy of the bespoke high scores should be made before an update happens, but that could be pushed off to the filesystem or backups, if those snapshot frequently enough.