Sorting Algorithms — Boring Until You Add Sound 118
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."
QuickBasic did this (Score:3, Informative)
Anybody who did their first programming steps with QuickBasic will remember that it came with a demo that did just this. Anyway, the videos are still fun to watch.
Re:QuickBasic did this (Score:5, Informative)
Ditto MS BASIC 7(?) on the old 1985 Amiga - included demos with sound.
Plus TV shows, especially scifi ones, do this all the time. The computers don't have to make noise but the audio engineer added the sound to keep the show from being dull.
Re:Sorting Out Sorting (Score:2, Informative)
Do you mean this? [youtube.com] Because as far as I can see, that one doesn't illustrate the sorting algorithm itself with sound. Disclaimer: I only watched the first three minutes.
Re:As a decided non-expert... (Score:5, Informative)
The heap sort actually has intermediate structure. If you watch carefully you can see that it has two phases, the first much shorter than the second. However, the structure isn't as visibly obvious as for merge sort.
If it had showed quicksort (I can't understand why it didn't) then you'd have seen some intermediate structure there too.
I also noticed that the selection sort wasn't as good as it could be. It's more efficient to select the largest and the smallest unsorted values on each pass - you halve the number of passes, and on each pass you do 50% more work, so overall it's a 25% improvement.
Re:Clown Sort (Score:2, Informative)
I know this as bogosort. Wikipedia also mentions random sort, shotgun sort and monkey sort as alternative names, but not clown sort. Also a Google search for "clown sort" doesn't seem to give sorting algorithm results, not even if I add algorithm as additional search term.
Re:Bugged bubble sort? (Score:2, Informative)
That optimization doesn't change the run-time complexity of the algorithm, it's still O(n^2). Usually bubble sort is taught without the optimization and once the student understands, you point out that particular optimization or try to get them to figure it out on their own.
Re:The sound of bubble sort (Score:2, Informative)
then your profs are kinda dumb, there are plenty of times when its acceptable to use bubble sort....
suppose you are on an embedded device, and you know that your inputs will always be limited by some factor, bubble sort also has rather good cache performance
Re:Try it with people (Score:4, Informative)
Re:No Quicksort? (Score:2, Informative)