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."
Re: (Score:3, Insightful)
Re: (Score:2)
Bloop, ping!
Re: (Score:1, Funny)
Wonderful. Just what we needed for the next generation of science fiction movies. Audible sorting!
Re: (Score:2, Funny)
Re: (Score:2)
Re: (Score:2)
I totally agree. Look, I am sorry to make this a "what has become of slashdot?" post, but WTF? Algorithms are INTERESTING. If using sound to illustrate sorting is interesting, then it is only interesting because the algorithms themselves are interesting, and you are unable to see that without the idiotic noises, through no fault of your own.
Re: (Score:1)
I watched/listened as I sucked the bong, the visual patterns converging certainly enhance the sounds, in a satisfying way. cough.
Re: (Score:1)
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: (Score:1)
Anybody who did their first programming steps with QuickBasic
fyi, remember that the freshman in high school right now were BORN in 1996. Heck, i started my BSEE in '01 and i barely made the cutoff for playing around with quickbasic. Though i was quite fond of the gorillas demo game... : )
Sorting Out Sorting (Score:3, Interesting)
Re: (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:Sorting Out Sorting (Score:4, Funny)
This guy did have not-annoying sounds related to the algorithm. Also the quality is much higher.
Re: (Score:2, Interesting)
My initial reaction was "Really? Seriously?? How does this make the algorithm any more interesting, easier to understand, or easier to remember? I mean hey - I like 80's console-sounds as much as the next guy, but they're not really adding anything."
Then it hit me that (apparently) many people haven't seen the algorithms visualized like this before. As someone who's been teaching this stuff for years, I've always handed out links to visualizations like this (even if they did lack the retro-hip sound eff
Re: (Score:1)
Re: (Score:1)
Well, given the new Web 2.0 interface, it might depend on your browser (I never tried it on anything but Firefox, so I don't know), not to mention that you can select between different interfaces, but if your Slashdot interface looks remotely like mine, there should be three possibilities to reply:
The first possibility has the advantage that it's always visible (provided that your browser supports it, also you probably have to have JavaScript enabled, and it might be invisible anyway if you are looking at t
Re: (Score:2)
Re: (Score:2)
No Quicksort? (Score:5, Insightful)
Feel like I'm complaining about a poll with a missing option, but, honestly ....:(
gus
Re: (Score:2, Funny)
I also noticed that they have Gnomesort, but not KDEsort. :-)
Re: (Score:2)
What would an XKCDsort look like?
Re: (Score:2, Informative)
Re: (Score:1)
What would an XKCDsort look like?
I dunno what it would look like, but when they run the sound algorithm on it, it would sound like some awesome song from Guitar Hero.
Re:No Quicksort? (Score:4, Insightful)
Re:No Quicksort? (Score:4, Funny)
I was looking for Bogosort [wikipedia.org] myself, actually.
Re: (Score:2)
Shear Sort (Score:4, Insightful)
The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.
Re: (Score:2)
The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.
And a wind tunnel.
Excellent (Score:2)
Just Play Popcorn by Hot Butter (Score:1, Insightful)
It doesn't even matter if it matches the sorting. All sorting algorithms will benefit from the playing of Popcorn.
Try it with people (Score:5, Funny)
There's a video on the internet somewhere. Free pint to the first person to find it.
Re:Try it with people (Score:4, Informative)
Re: (Score:2)
Re: (Score:3, Funny)
Not boring, more interesting (Score:2)
There was a dismissive comment recently modded down about being "easily amused" by the bleeps and bloops, well that may be so, but it sure adds flavor to the process.
I can imagine how various sorting operations work in my head but I never thought about what they might sound like, and that makes them just a little more interesting. :-)
Re: (Score:2)
I never thought about what they might sound like either, but now that I know what they sound like I can't help but wonder what they might taste like. I'm betting quicksort tastes just like snozzberry.
As a decided non-expert... (Score:3, Interesting)
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.
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.
60s/70s music (Score:2)
A lot of them sound like something you'd hear at the beginning/end of some song from the 60s or 70s.
Re: (Score:2)
some song from the 60s or 70s.
That only covers 20 years worth of music. Can you be more specific?
http://en.wikipedia.org/wiki/Popcorn_(instrumental) [wikipedia.org]
Re: (Score:1)
You mean kind of like the start of the 60's "Reflections" by the Supremes?:
http://www.youtube.com/watch?v=yUuERNcQ8gk [youtube.com]
The sound of bubble sort (Score:5, Funny)
That's strange. When I listen to the sound of bubble sort all I hear is one of my college professors threatening to hunt me down and kill me in my sleep if I ever use it.
Re: (Score:1, Funny)
That's strange. When I listen to the sound of bubble sort all I hear is one of my college professors threatening to hunt me down and kill me in my sleep if I ever use it.
I just hear my bong.
Re: (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: (Score:2)
Re: (Score:3, Interesting)
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 (muc
Re: (Score:2)
Re: (Score:2)
Yep, I've seen optimized implementations of quicksort which drop down to bubble sort when there's only three or four elements in the current subdivision.
PS: The one in the video could easily be optimized to go twice as fast and would beat some of the others if you did.
Re: (Score:2)
The bubble sort one actually did sound kind of bubbly.
Could be Better (Score:2)
I'm not a big fan of these sounds, but I like the idea.
Merge Sort - traffic sound
Bubble Sort - blowing bubble sound from bubble bobble
Insert Sort - coin slot
Select sort - crain game sounds
Gnome Sort - 7 dwarfs singing Hi-Ho, Hi-Ho
At least that way you can associate sounds with different algorithm types and remember what they are.
Hardly new (Score:2)
Re: (Score:2)
...Mac OS X.
Gah, meant Mac OS < X
Diagnostics (Score:5, Interesting)
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.
Clown Sort (Score:2)
My favorite sort. Randomly arrange items until they are in order. Would the appropriate music be some type of carnival melody?
Re: (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: (Score:1)
Bugged bubble sort? (Score:3, Interesting)
Re: (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: (Score:2)
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.
I haven't yet run across a comp. sci. text that describes the bubble sort without the "optimization". I've always thought it was an intrinsic part of the bubble sort algorithm.
What Fun! (Score:1)
It feels like your head is going to explode at the end, and the final pass is the sound of brain matter splattering across the pages of your algorithms textbook.
Visual Aids (Score:1, Interesting)
I found http://www.sorting-algorithms.com/ to be useful for looking at how sorting works, too.
Also fun: porttwiddle (Score:1, Interesting)
http://wolfbell.com/projects/index.html [wolfbell.com] - 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! ;-)
Sorting is fun (Score:1)
Re: (Score:2)
[quote]I sorta like it.[/quote]
I have mod points but couldn't find 'dad joke'
Which sounds best? (Score:2)
They should bring back the Slashdot poll to discuss which of these sorting algorithms sounds best. (IMO, Insertion sort, bubble sort, and Heapsort sound coolest.)
Re: (Score:2)
Very Old Idea (Score:2)
Sorting is a waste of time (Score:2)
WTB New slashdot CSS/JavaScript programmer. The current one really blows.
Re:Sorting is a waste of time (Score:5, Insightful)
If you think all that time examining sorting algorithms was intended to teach you about sorting, then you indeed missed the point. Programming courses spend a lot of time on sorting because it is a common task that can be easily understood, but for which there are a lot of different algorithms with very different performance characteristics. The point is to teach algorithm analysis skills.
Judging from the quality of code I encounter regularly, though, you're far from alone in failing to pick up that lesson.
Re: (Score:2)
Exactly. The only time I ever looked at sorting algorithms was in university. For the last 20+ years, all I ever did was call some sort() or qsort() library function.
Considering whether to apply a Schwartzian Transform was probably the most I ever thought about sorting.
Re: (Score:2)
The point is to teach algorithm analysis skills.
Well, that, and to teach that their performance isn’t the only metric that you can judge them by... for instance, the “best” (fastest) sorting methods also tend to be the most inefficient in terms of how much extra memory they need. If you swap elements with XOR, a bubble sort only requires 1 extra bit to tell it when it’s finished.
Re: (Score:2)
sorting rules (Score:1)
Boring?? (Score:2)
I read Knuth for fun... I don't get this notion of algorithms being "boring"...
Fairly dry? (Score:1)
What do you mean it's fairly dry? Sorts are awesome!
Respect the sorting algorithms!
Sorting real objects (Score:4, Interesting)
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
Re: (Score:2)
Well, to be pedantic, that's not *strictly* quicksort. It's a two bin radix sort. The only difference, of course, is that in quicksort you pick your pivot based on some item(s) in your set, and in radix you select the boundary based on properties of the data distribution. I only mention it because I *have* seen something that uses radix sort on physical objects: an old punch card sorter.
Re: (Score:2)
I always used a variation of the aptly name Library Sort: Throw all the books on the floor and then put them roughly in the right position on the shelf, leaving gaps. After all, you have almost infinite scratch space.
Re: (Score:1)
Re: (Score:2)
I always do an insertion sort until it starts getting inefficient (pretty soon usually) then abandon my sorted stack and start a new one. Once I have sorted everything into small sorted stacks, I merge sort them two at a time to get larger sorted stacks, then repeat until I have only one sorted pile.
Re: (Score:1)
Re: (Score:1)
I think it's more about whether your fellow students have any sense than whether or not they know about quicksort.
What about Random Sort (Score:2)
What about random sort, where you swap 2 random values and test to see if it is sorted. I assume it would sound like static, probably white noise (as opposed to pink noise).
Re: (Score:2)
I would optimize that by only swapping the values if they’re out of order:
Really? (Score:1)
Actual code and performance analysis shouldn't be boring or "dry" to someone who aspires to be a computer scientist or specifically a programmer, especially not the first time they learn about it...
Re: (Score:2)
I do not think the sound adds anything, myself. The visuals could be helpful if played more slowly, but the sound? It does not help me, and as used in TFA, it is even an annoying noise.
An old boss of mine used to work on a large computer which was used to control the activities inside a sawmill. It was made up of several thousand magnetic reed relays to perform the logic. The program itself was keyed into the system via about 1000 throw switches. The entire machine was devoid of silicon. This was pretty "
Re: (Score:1)
Your boss taking months to "get used" to the sound is important here, and the fact that he was using it to diagnose problems, not for learning how the machine works conceptually.
Sure, anyone can probably very easily tell a badly broken engine (no sound, heavy thumps, clacking, croaking etc) from a working one - even after experiencing a working one only once. But that is all - you do not learn at all how an engine works from hearing it, nor can you omit the prior learning.
We use our spatially accurate sense
Listening to music (Score:2)
I was listening to some dance/trance music. I though I had a problem with my speakers playing the video because I didn't notice any new sounds :o
Boring? (Score:2)
Sorting may be boring to implement repeatedly (tedium by definition), but I found learning the various standard sorting algorithms to be pretty interesting, and a great practical introduction to pointers.
Programming is first and foremost about problem solving, regardless of whether you're creating a game or a spreadsheet, and sorting is a common problem. If you find learning (and discovering) how to solve problems effectively and efficiently to be boring, then you're probably pursuing the wrong line of wor
If the implementation was written in C (Score:1)
the authors should listen to Franz Schubert's Symphony Number 9.
Where are the llamas? (Score:2)
Nice vids but where are the llamas [wikipedia.org]?
For all you young whippersnappers: these sounds resemble the noises emanating from a series of C=64 games by Jeff 'Yak' Minter [wikipedia.org], one of the better known software developers from the 80's.
Re: (Score:2)
It's more efficient if the vectors holds pointers instead of data.
It's more efficient if you don't use std::vector.