Sorting algorithms are a common exercise for new programmers, and for good reason: they introduce many programming fundamentals at once, including loops and conditionals, arrays and lists, comparisons, algorithmic complexity, and the tradeoff between correctness and performance. As a fun Christmas project, [Scripsi] set out to implement twelve different sorting algorithms over twelve days, using Christmas lights as the sorting medium.
The lights in use here are strings of WS2812 addressable LED strips, with the program set up to assign random hue values to each of the lights in the string. From there, an RP2040-based platform will step through the array of lights and implement the day’s sorting algorithm of choice. When operating on an element in the array the saturation is turned all the way up, helping to show exactly what it’s doing at any specific time. When the sorting algorithm has finished, the microcontroller randomizes the lights and starts the process all over again.
For each of the twelve days of Christmas [Scripsi] has chosen one of twelve of their favorite sorting algorithms. While there are a few oddballs like Bogosort which is a guess-and-check algorithm that might never sort the lights correctly before the next Christmas (although if you want to try to speed this up you can always try an FPGA), there are also a few favorites and some more esoteric ones as well. It’s a great way to get some visualization of how sorting algorithms work, learn a bit about programming fundamentals, and get in the holiday spirit as well.
And the usual result is new programmer gets overwhelmed and learns bugger all.
Ugly truth is most folks who code are not fedora-wearing 140 IQ successors to Richard Stallman.
And they then just use the ‘sort’ command in whatever language they are using, and get on with the task at hand.
True, but as I discovered with Quicksort, there can still be edge cases where the programming language’s algorithm may fail. Gaining a little understanding about how things work under the hood might help you deal with those thorny bugs.
Learning about sorting techniques can make the programmer aware of concepts and if they are ever in a tight spot, they can implement less than a full sorting algo, that will get them what they need and save cycles or memory. Maybe they will never use it, but maybe the will. Not everything worth learning is of immediate practical value.
Honestly, sorts are the lowest hanging fruit of algorithms, beyond “print the numbers from one to ten” and “read a dozen numbers and find the largest/smallest/average”. Generally introduced after control structures are well hammered (loops, conditionals, and the like) and no more kiddie toy projects will add any value.
Most elementary sorts use nested loops of depth two and have very straightforward conditions and invariants. The end result is easy to check. the changes in behaviour due to changes in input sets are easy to relate to the algorithms.
Or would you consider that the first non-trivial algorithm should be Floyd-Warshall, since it had applications in web searching and deep learning?
If you think it makes programming overwhelming, then you really need to consider whether you should be saying anything at all regarding software.
(This will be my only comment in this post, as my asbestos suit is at the dry cleaner, being de-fuelled with carbon-tet)
Few years back (2021) I’ve run head-on into a need to quickly (and rather resource-efficiently) sort few tens thousands records in some kind of order as they are arriving from a SQL run. BTree was the answer, auto-sorting whilst being added to a hash table for later retrieval/reading, and things were awesome once done. Luckily for me I’ve scored indexed double integer field that was asking just for such solution (luckily because not always that’s the thing, a lot of data is stored as plain vanilla unindexed strings, and strings are notoriously hard to brute force into sorting quickly – unless pre-indexed properly, or scaled down to some kind of easily indexable Soundex, and indexing strings usually takes quite a lot of space, so usually done sparingly, if at all; date/time stamps fare slightly better, since almost always can be forced into indexed floats).
Data massaging is almost always like that – there is no guarantee that the database engine will be up for the task of partioning on the fly (ie dynamic execution plans, not baked ones like in views), so that would have to be handled down the stream. Surprisingly, ordinary Java VM handled tens thousands of records per fetch for ~ few dozens of active sessions no problem. We’ve tested all users running different heavy data lifting (and sorting), no problem, BTrees shined each and every time.
This project wasn’t just about learning to program sorting algorithms (although it was fun to discover the sheer variety of ways to solve the same basic problem). It was also about the challenge of designing, programming, documenting and publishing successive releases on a regular and tight schedule. The stakes were low, but I still learnt a lot and enjoyed it!
It occurs to me that this could be used to signal fellow aficionados that live nearby – put this up in a window and wait for someone to stand staring thoughtfully at it for far too long before asking “is this a…quicksort….or something?”
I may give it a go myself.
Have you used Jira?
Anybody else disappointed that actual, physical Christmas lights weren’t the items being sorted?
It’s still a useful display method, just not quite what I’d been expecting based on the title of this article…