Forgot your password?
typodupeerror
Programming

Sorting Algorithms — Boring Until You Add Sound 118

Posted by Soulskill
from the bloop-bleep-bloop dept.
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."
This discussion has been archived. No new comments can be posted.

Sorting Algorithms — Boring Until You Add Sound

Comments Filter:
  • QuickBasic did this (Score:3, Informative)

    by Bananenrepublik (49759) on Friday August 20, 2010 @01:22PM (#33315952)

    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.

    • by commodore64_love (1445365) on Friday August 20, 2010 @01:42PM (#33316300) Journal

      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.

    • by afex (693734)

      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)

    by SilverEyes (822768) on Friday August 20, 2010 @01:26PM (#33316014)
    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).
    • Re: (Score:2, Informative)

      by maxwell demon (590494)

      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.

      • by SilverEyes (822768) on Friday August 20, 2010 @02:13PM (#33316714)
        I did watch it again after I posted my comment, I was wrong. I misremembered the video. The annoying sounds are unrelated to the algorithm.

        This guy did have not-annoying sounds related to the algorithm. Also the quality is much higher.
        • Re: (Score:2, Interesting)

          by MikeTheGreat (34142)

          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

          • by perlmangle (49439)
            You reply to the main story, up top. Look for the box that contains "The Fine Print:" and then hit 'reply'.
          • 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

      • Obligatory watch on the first algorithm course at my local university.
        • We always showed this in a continuous loop during the engineering open house. Free popcorn was provided by the local branch of the ACM.
  • No Quicksort? (Score:5, Insightful)

    by gus goose (306978) on Friday August 20, 2010 @01:28PM (#33316032) Journal

    Feel like I'm complaining about a poll with a missing option, but, honestly ....:(

    gus

  • Shear Sort (Score:4, Insightful)

    by jellomizer (103300) on Friday August 20, 2010 @01:28PM (#33316038)

    The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.

    • by Abstrackt (609015)

      The Shear Sort is one of my favorite sorts out there. Although you will need an orchestra to play it.

      And a wind tunnel.

  • That is awesome.
  • by Anonymous Coward

    It doesn't even matter if it matches the sorting. All sorting algorithms will benefit from the playing of Popcorn.

  • by twoshortplanks (124523) on Friday August 20, 2010 @01:32PM (#33316130) Homepage
    It's always more fun to do this with real people (sort by height, for example). The London Perl Mongers tried this as a drinking game: You get enough people down the pub (or, in one this case, outside a bar in portugal during conference season) and apply booze. Then bubble sort them as a group (lots of shouting Stay! Switch!.) Add drinking penalties when people screw up the algorithm. You get the idea.

    There's a video on the internet somewhere. Free pint to the first person to find it.

  • 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. :-)

    • 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.

  • by KingAlanI (1270538) on Friday August 20, 2010 @01:33PM (#33316156) Homepage Journal

    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.

    • by pjt33 (739471) on Friday August 20, 2010 @01:44PM (#33316360)

      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.

  • A lot of them sound like something you'd hear at the beginning/end of some song from the 60s or 70s.

  • by Anonymous Coward on Friday August 20, 2010 @01:38PM (#33316218)

    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)

      by MrMe (172559)

      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)

      by Anonymous Coward

      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

    • by lewiscr (3314)
      Bubble sort does have it's uses; if you know the array is <= 3 elements, Bubble Sort wins.
      • Re: (Score:3, Interesting)

        by jfengel (409917)

        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

        • This is why I always liked Heapsort. In place sorting in an array (O(n) space) and optimal time complexity (O(n*lg(n)) steps). If you bother to learn Heapsort well, you don't really *need* any other sorting algorithm.
      • by Joce640k (829181)

        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.

    • by sconeu (64226)

      The bubble sort one actually did sound kind of bubbly.

  • 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.

  • My CS lecturer [stanford.edu] prepared a number of these for an intro CS course. I took the class back in '06-'07, but IIRC the videos were taken from Mac OS X. That said, it is pretty neat.
  • Diagnostics (Score:5, Interesting)

    by PPH (736903) on Friday August 20, 2010 @01:42PM (#33316308)

    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.

  • 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)

      by maxwell demon (590494)

      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.

  • Bugged bubble sort? (Score:3, Interesting)

    by Anaerin (905998) on Friday August 20, 2010 @01:51PM (#33316438)
    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.
    • Re: (Score:2, Informative)

      by Anonymous Coward

      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.

      • by BitterOak (537666)

        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.

  • The Selection Sort's soundtrack was quite fun!

    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)

    by Anonymous Coward

    I found http://www.sorting-algorithms.com/ to be useful for looking at how sorting works, too.

  • by Anonymous Coward

    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! ;-)

  • I sorta like it.
  • 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.)

    • by treeves (963993)
      I liked selection sort the best. Musically, the "piece" constantly seems to accelerate leading to a pleasing conclusion. But merge sort was a more complex piece.
  • The sounds aren't quite the same, but Quick Basic for MS DOS had a program in the Examples folder that does almost exactly this. Generates random data and shows various sorting techniques on it visually, playing a different tone for each comparison made. Not as much data (since it had to graph it in 320x200), much slower in a 286, and sound was done by internal speaker, but same idea at least.
  • Meh, sorting should be covered in about 2 hours in any programming course. I spent an entire quarter on sorting back in college and I still to this day cannot see the point of repeating the same exercise over and over again, just with a different sorting algo. But perhaps my professor was just retarded (that was the general consensus between the students anyway).

    WTB New slashdot CSS/JavaScript programmer. The current one really blows.
    • by mea37 (1201159) on Friday August 20, 2010 @02:41PM (#33317024)

      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.

      • by rrohbeck (944847)

        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.

      • 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.

        • Heapsort is optimal in time and space. It can be mildly complicated to code if you're not careful, but the whole thing can be done in one function without recursion, so you don't even have stack overhead with it. Of course, if your sorting needs are wildly complicated (like, you're a developer for Oracle or something) then others may make more sense. But for your average run-of-the-mill array sorting, Heapsort should be all you ever really need.
  • Sorting may be boring, but it is an awesome way to really dive in to a language(at least c++).
  • I read Knuth for fun... I don't get this notion of algorithms being "boring"...

  • What do you mean it's fairly dry? Sorts are awesome!

    Respect the sorting algorithms!

  • Sorting real objects (Score:4, Interesting)

    by spaceyhackerlady (462530) on Friday August 20, 2010 @02:42PM (#33317038)

    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

    • 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.

    • by rrohbeck (944847)

      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.

      • I thought you were going to describe Library Sort as it always seemed to me: Throw all of the books on the floor and then jam them on the shelf with no gaps and plenty of books from incorrect sections randomly scattered throughout. Oh, and sprinkle horizontal books liberally on top.
    • 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.

    • I know 0; however, I use mergesort (bottom-up variety) with great regularity for arranging cards/books/etc.
    • I also did this when I worked in the library in college. Although it's true that I took some programing classes, I think this is just common sense. Most of my student coworkers were social science or liberal arts majors, and as far as I saw, they all did the same thing.

      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, 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).

    • I would optimize that by only swapping the values if they’re out of order:

      <html>
      <body>
      <canvas id="paintbox" height=480 width=640 />

      <script>
      function sorted(a) {
      for (var i = 0; i < a.length;) if (a[i] > a[++ i]) return false;
      return true;
      }

      function sort_values() {
      if (!sorted(a)) {
      var i = (Math.random() * (a.length + 1)), j = (Math.random() * a.length), t;

      if (j >= i) j ++

  • 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.

    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...

    • by pclminion (145572)

      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 "

      • by Radtoo (1646729)

        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

  • 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

  • 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

  • the authors should listen to Franz Schubert's Symphony Number 9.

  • 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.

In a consumer society there are inevitably two kinds of slaves: the prisoners of addiction and the prisoners of envy.

Working...