Slashdot Mirror
Sorting Algorithms — Boring Until You Add Sound
An anonymous reader writes "Anyone who's ever taken a programming course or tried to learn how to code out of a book will have come across sorting algorithms. Bubble, heap, merge — there's a long list of methods for sorting data. The subject matter is fairly dry. Thankfully, someone has found a way to not only make sorting more interesting, but easier to remember and understand, too."
Does anyone remember "Sorting Out Sorting" (1980)? Best sorting video ever made. This is the same thing, it's good, but it was done thirty years ago. Also, "Pointy Does Pointers" (not an adult film, I swear).
Interesting.
Ted Bundy would disagree
One thing this seems to show me (at least the video does)
the rate of completion - how much is sorted by each point in the process
the algorithms seem to all do that a bit differently; some have most of the work completed in the beginning, some in the end.
Most seem to take one piece of data and plunk it right in order; the merge sort seems to be the only one with intermediate groupings.
and there's one final pass to make sure the data's in order.
I notice different sorting processes are appropriate for different RL sorting situations.
I listen to both RIAA and non-RIAA stuff if I like the music, tangential business/politics nonwithstanding.
One interesting application of such audible/visual representations could be for diagnostic reasons.There are numerous cases where experienced observers can spot patterns or anomalies in patterns that machine algorithms have trouble with.
One example I was involved in years ago at Boeing was a tool for diagnosing a large switch matrix used in a piece of automated test equipment. Each output could be tied to a high, low or open signal, driven from a controller over an HPIB bus. Failure modes included not only an output stuck high, low or open, but address bus problems where some lines would cause passive failures or activate more than one pin. After watching a poor engineer go through a suspect matrix panel for over a day, entering a command on the bus, finding the pin on a patch panel, sticking a voltmeter on it, over and over a few thousand times, we came up with a solution. Bi-colored LEDs wired to a patch panel and a program to exercise the matrix with a series of address patterns. An observer could spot a single bad switch or a hung address bus line in a few seconds just by looking for an anomaly in a couple of checkerboard and other patterns.
Have gnu, will travel.
The bubble sort used here is kinda bogus. It iterates over the whole set on every pass, which it doesn't need to. It only needs to go over dataset-(pass-1) items. I have a feeling this will change the "sound" of the bubble sort in this example.
I found http://www.sorting-algorithms.com/ to be useful for looking at how sorting works, too.
http://wolfbell.com/projects/index.html - Porttwiddle is an add-on module to a one-disk linux router project that will play sounds of different frequency depending on the port number. You'll never miss a portscan again! ;-)
As an undergrad I worked in the university library to earn a bit of spending money, and one of my tasks was sorting books to put them back on the shelves. My colleagues used selection sort. I didn't.
I did a first pass through the books. Two piles, typically A-L, M-Z. Then a second pass, A-D, E-L, M-R, S-Z. And so on, until the piles were small enough I could go through them and put them on the shelf in order.
How many people do you know who actually use quicksort to sort real objects?
...laura
And that's not uncommon. There are plenty of circumstances where you may have a large number of short lists floating around. Say, a list of a person's children, which will be less than 4 in 99% of cases and even the extreme cases aren't going to kill you. There may be many instances of the list, but each will be small.
Sorting those lists via some O(n^2) sort is lower overhead than building up fancy data structures. Especially if you're building the lists incrementally, such as via an insertion sort (much like an incremental bubble sort).