5 ms·

What different sorting algorithms sound like

231 points by pavs 16y ago

muyyatin 16y ago
It would be interesting to listen to graph algorithms.
- scotth 16y ago
  What do you imagine would determine frequency?
  - muyyatin 16y ago
    For example in depth first search, the depth.
    - dhs 16y ago
      I like that. And in breadth first search, one could use a filter on a saw wave to have the breadth of the frequency spectrum manipulated by the search.
meatmanek 16y ago
What, no quick sort? And no heap sort?
- Batsu 16y ago
  There was a link to the heapsort at the end: http://www.youtube.com/watch?v=iXAjiDQbPSw http://www.youtube.com/watch?v=iXAjiDQbPSw
  - moultano 16y ago
    That is by far the coolest sounding of the bunch.
Technophilis 16y ago
Merge sort's sound is actually recursive.
keyle 16y ago
That was really cool. Is the speed indicative of the speed of the sort?
- simonista 16y ago
  I'm not sure, but the visual part of the videos looks a lot like visualizations I've seen in algorithms classes where the speed does represent the speed of the sort. So I'd guess that it does here as well. These are really great. As a musical person it engrained these concepts that much deeper for me. My wife, who is not much of a computer science person like the merge sort the best.
- frio 16y ago
  Given that the width of the elements being sorted changes (therefore there are more/less elements in different visualisations), I'd say no.
- mr_twj 16y ago
  I would say it's likely. There are all sorts (pun intended) of optimizations you can do for each algorithm, but at the textbook level, I could say they seemed typical as far as speed expectancy goes. My rough estimates for the times were (in seconds): insert: ~10, bubble: ~27, selection: ~18, merge: ~17, and gnome: ~19. I have only written inserts, bubbles, and selections; with bubble being slowest and insert being the fastest, my limited experience agrees with the video. Note: the merge algorithm appeared to have sorted a different data set.
mhansen 16y ago
There's a lot of effort been put in to this, I like it. I love that you can hear the bubbling in bubble sort :D
- marktucker 16y ago
  I noticed that too! Good stuff.
vijaydev 16y ago
Cool job! Gnome Sort - now that's new to me!
snprbob86 16y ago
That was super cool! I really enjoyed how my brain started matching the sound and the bar heights in such a way that by the end I said "of course that one sounds like that".
momokatte 16y ago
This makes me want to sort something. The loose change strewn all over my desk. The contents of my fridge. The words on this page. Anything.
- petdog 16y ago
  Anything. The The The This all change contents desk. fridge. loose makes me my my of on over page. something. sort strewn this to want words
  - jacquesm 16y ago
    all Anything. change contents desk. fridge. loose makes me my my of on over page. something. sort strewn The The The This this to want words
ramki 16y ago
where is quicksort?
- jacquesm 16y ago
  Too fast to hear. But nice to look at: http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=related http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=relat...
  - sesqu 16y ago
    Bullshit on the too fast. Mergesort never needs more comparisons than quicksort, and mergesort was featured.
    - jacquesm 16y ago
      Errm. Yes. I know that. It was a joke...
      - sesqu 16y ago
        I've noticed that we don't share the same sense of humour. Generally speaking, I've seen too many people assert that quicksort is blazingly fast to believe all of them were joking. It doesn't particularly help that the major sorting algorithms are severely fragmented, because people optimize variously for stability, time, space, comparisons, swaps, cache locality, parallelizability, best case, worst case, average case, amortized average case, arrays, lists, integers, objects...
        jacquesm 16y ago
        quicksort has very bad performance on the wrong data. But on the kind of data that the test showed it would perform more or less on par with merge sort. To suggest that quick sort would be that much faster than merge sort that you couldn't hear it when there are obviously quite a few steps is to me more than enough reason to assume a joke rather than a serious answer. Anyway, humour is a hard thing to get across online, I should have added a ;) at a minimum apologies for that, also HN seems to frown on humor (even though every now and then there are some really good jokes here http://news.ycombinator.com/item?id=1597571 http://news.ycombinator.com/item?id=1597571 ) this one was reasonably lame but the subject wasn't all that serious to begin with. Sorting is enough of an issue that Knuth devoted the better part of a very thick book to it and to this day there are plenty of people that think that 'one size fits all'. The more you know about your data the faster you can sort it.
transmit101 16y ago
Disclaimer: sorting algorithms can sound like just about anything, depending which parameters you map to which sounds. This is just a simple example of data sonification, albeit with some nice visualisation too, and a subject matter which appeals to the computer scientists in the room.
- Tichy 16y ago
  I thought the values to be sorted would be the amplitude of the sound wave, and the value currently touched by the algorithm would be played in each step. Of course you could still pick arbitrary values and arbitrary start orderings.
- noncee22343 16y ago
  No. Under some simple guidelines, which the model follows, the sorting algorithms won't sound like just about anything. If you sort random permutations of the values [1, n], and map some monotonic property to the values, then not only are there provably some sounds which certain algorithms make that others don't, but more generally there are 'average case' signatures for each algorithm that give them their own recognizable cadences, and that is exactly what this video is demonstrating. That you can use a 'boop' or a 'beep' or 'buzz' or invert the monotonicity is obvious and irrelevant.
Synaesthesia 16y ago
I think Mathematica can be used to make "audiolizations" really easily. They include one of the Riemman Zeta function as a demo. It sounds really cool (sorry I can't find a link, I'll try upload it)
willvarfar 16y ago
bubble sort sounds like someone chanting "DEVELOPERS! DEVELOPERS! DEVELOPERS!" !!!! :D
- pavs 16y ago
  http://www.youtube.com/watch?v=KMU0tzLwhbE http://www.youtube.com/watch?v=KMU0tzLwhbE
hyyypr 16y ago
Awesome link. It reminds me of a website showing a matrix with visualizations of several sorting algorithms: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ (which was posted somewhere here iirc).
hubb 16y ago
i know the choice of sounds was arbitrary, but it nonetheless reminded me of the seal calls of 'encounters at the end of the world': http://www.youtube.com/watch?v=SORza1fqQGk http://www.youtube.com/watch?v=SORza1fqQGk
Luc 16y ago
At times this sounds a lot like an old Williams shoot'em-up arcade game, like Defender for example.
ralph 16y ago
Why does the bubble sort continue to the end of the array on every pass, when it could stop one earlier each time?
tfmorris 16y ago
Interesting, but not new. Mark Brown did this two decades ago at DEC SRC (and probably others before him). http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-76A.html http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-76A.html
ysorter78 16y ago
See another experiment: http://www.youtube.com/watch?v=ol5ml9e2THw http://www.youtube.com/watch?v=ol5ml9e2THw It sonifies the following algorithms (from http://www.algolist.net/Algorithms/ http://www.algolist.net/Algorithms/ ) - Bubble sort - Selection sort - Insertion sort - Quicksort You can also see their sonograms.
jassadat 16y ago
Here is a live version of the sounds of various sorting algorithms. Done using HTML 5 audio - http://bit.ly/sort-sound http://bit.ly/sort-sound

231 points by pavs 16y ago

muyyatin 16y ago

It would be interesting to listen to graph algorithms.

scotth 16y ago
What do you imagine would determine frequency?
- muyyatin 16y ago
  For example in depth first search, the depth.
  - dhs 16y ago
    I like that. And in breadth first search, one could use a filter on a saw wave to have the breadth of the frequency spectrum manipulated by the search.

meatmanek 16y ago

What, no quick sort? And no heap sort?

Batsu 16y ago
There was a link to the heapsort at the end: http://www.youtube.com/watch?v=iXAjiDQbPSw http://www.youtube.com/watch?v=iXAjiDQbPSw
- moultano 16y ago
  That is by far the coolest sounding of the bunch.

Technophilis 16y ago

Merge sort's sound is actually recursive.

keyle 16y ago

That was really cool. Is the speed indicative of the speed of the sort?

simonista 16y ago
I'm not sure, but the visual part of the videos looks a lot like visualizations I've seen in algorithms classes where the speed does represent the speed of the sort. So I'd guess that it does here as well. These are really great. As a musical person it engrained these concepts that much deeper for me. My wife, who is not much of a computer science person like the merge sort the best.
frio 16y ago
Given that the width of the elements being sorted changes (therefore there are more/less elements in different visualisations), I'd say no.
mr_twj 16y ago
I would say it's likely. There are all sorts (pun intended) of optimizations you can do for each algorithm, but at the textbook level, I could say they seemed typical as far as speed expectancy goes. My rough estimates for the times were (in seconds): insert: ~10, bubble: ~27, selection: ~18, merge: ~17, and gnome: ~19. I have only written inserts, bubbles, and selections; with bubble being slowest and insert being the fastest, my limited experience agrees with the video. Note: the merge algorithm appeared to have sorted a different data set.

mhansen 16y ago

There's a lot of effort been put in to this, I like it. I love that you can hear the bubbling in bubble sort :D

marktucker 16y ago
I noticed that too! Good stuff.

vijaydev 16y ago

Cool job! Gnome Sort - now that's new to me!

snprbob86 16y ago

That was super cool! I really enjoyed how my brain started matching the sound and the bar heights in such a way that by the end I said "of course that one sounds like that".

momokatte 16y ago

This makes me want to sort something. The loose change strewn all over my desk. The contents of my fridge. The words on this page. Anything.

petdog 16y ago
Anything. The The The This all change contents desk. fridge. loose makes me my my of on over page. something. sort strewn this to want words
- jacquesm 16y ago
  all Anything. change contents desk. fridge. loose makes me my my of on over page. something. sort strewn The The The This this to want words

ramki 16y ago

where is quicksort?

jacquesm 16y ago
Too fast to hear. But nice to look at: http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=related http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=relat...
- sesqu 16y ago
  Bullshit on the too fast. Mergesort never needs more comparisons than quicksort, and mergesort was featured.
  - jacquesm 16y ago
    Errm. Yes. I know that. It was a joke...
    - sesqu 16y ago
      I've noticed that we don't share the same sense of humour. Generally speaking, I've seen too many people assert that quicksort is blazingly fast to believe all of them were joking. It doesn't particularly help that the major sorting algorithms are severely fragmented, because people optimize variously for stability, time, space, comparisons, swaps, cache locality, parallelizability, best case, worst case, average case, amortized average case, arrays, lists, integers, objects...
      - jacquesm 16y ago
        quicksort has very bad performance on the wrong data. But on the kind of data that the test showed it would perform more or less on par with merge sort. To suggest that quick sort would be that much faster than merge sort that you couldn't hear it when there are obviously quite a few steps is to me more than enough reason to assume a joke rather than a serious answer. Anyway, humour is a hard thing to get across online, I should have added a ;) at a minimum apologies for that, also HN seems to frown on humor (even though every now and then there are some really good jokes here http://news.ycombinator.com/item?id=1597571 http://news.ycombinator.com/item?id=1597571 ) this one was reasonably lame but the subject wasn't all that serious to begin with. Sorting is enough of an issue that Knuth devoted the better part of a very thick book to it and to this day there are plenty of people that think that 'one size fits all'. The more you know about your data the faster you can sort it.

transmit101 16y ago

Disclaimer: sorting algorithms can sound like just about anything, depending which parameters you map to which sounds. This is just a simple example of data sonification, albeit with some nice visualisation too, and a subject matter which appeals to the computer scientists in the room.

Tichy 16y ago
I thought the values to be sorted would be the amplitude of the sound wave, and the value currently touched by the algorithm would be played in each step. Of course you could still pick arbitrary values and arbitrary start orderings.
noncee22343 16y ago
No. Under some simple guidelines, which the model follows, the sorting algorithms won't sound like just about anything. If you sort random permutations of the values [1, n], and map some monotonic property to the values, then not only are there provably some sounds which certain algorithms make that others don't, but more generally there are 'average case' signatures for each algorithm that give them their own recognizable cadences, and that is exactly what this video is demonstrating. That you can use a 'boop' or a 'beep' or 'buzz' or invert the monotonicity is obvious and irrelevant.

Synaesthesia 16y ago

I think Mathematica can be used to make "audiolizations" really easily. They include one of the Riemman Zeta function as a demo. It sounds really cool (sorry I can't find a link, I'll try upload it)

willvarfar 16y ago

bubble sort sounds like someone chanting "DEVELOPERS! DEVELOPERS! DEVELOPERS!" !!!! :D

pavs 16y ago
http://www.youtube.com/watch?v=KMU0tzLwhbE http://www.youtube.com/watch?v=KMU0tzLwhbE

hyyypr 16y ago

Awesome link. It reminds me of a website showing a matrix with visualizations of several sorting algorithms: http://www.sorting-algorithms.com/ http://www.sorting-algorithms.com/ (which was posted somewhere here iirc).

hubb 16y ago

i know the choice of sounds was arbitrary, but it nonetheless reminded me of the seal calls of 'encounters at the end of the world': http://www.youtube.com/watch?v=SORza1fqQGk http://www.youtube.com/watch?v=SORza1fqQGk

Luc 16y ago

At times this sounds a lot like an old Williams shoot'em-up arcade game, like Defender for example.

ralph 16y ago

Why does the bubble sort continue to the end of the array on every pass, when it could stop one earlier each time?

tfmorris 16y ago

Interesting, but not new. Mark Brown did this two decades ago at DEC SRC (and probably others before him). http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-76A.html http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-76A.html

ysorter78 16y ago

See another experiment: http://www.youtube.com/watch?v=ol5ml9e2THw http://www.youtube.com/watch?v=ol5ml9e2THw It sonifies the following algorithms (from http://www.algolist.net/Algorithms/ http://www.algolist.net/Algorithms/ ) - Bubble sort - Selection sort - Insertion sort - Quicksort You can also see their sonograms.

jassadat 16y ago

Here is a live version of the sounds of various sorting algorithms. Done using HTML 5 audio - http://bit.ly/sort-sound http://bit.ly/sort-sound