The Sound of Sorting - "Audibilization" and Visualization of Sorting Algorithms

Autor: Timo Bingmann
17 diciembre 2019

Categoría: Software

Sorting algorithms are an essential chapter in undergraduate computer science education. Due to their easy to explain nature and fairly straight-forward analysis, this set of algorithms offers a convenient introduction to the methods and techniques of theoretical computer science and algorithm analysis.

This web page presents my own demo program for sortings algorithms, called "The Sound of Sorting", which both visualizes the algorithms internals and their operations, and generates sound effects from the values being compared. See below for YouTube videos created with the demo.

The demo is implemented using the cross-platform toolkits wxWidgets and SDL, can be executed on Windows, Linux and Mac, and runs in real time.

All of the sorting algorithms are implemented in the SortAlgo.cpp.

Since November 2013, there is also the SoS-CheatSheet.pdf  which contains pseudo-code of a small selection of the algorithms.

On 2013-10-24, the viral YouTube video infected the front page of my current employer: the Department of Informatics at the Karlsruhe Institute of Technology (KIT), which is of course whom I originally made the demo program for. See the blog post about this occasion for another more technical description of the sorting demo program. [Added 2013-10-25]

See the README file below for information about using the program.


Prior Sorting Demos

There are many resources on the Internet about sorting algorithms, among them are Wikipediaanimated sorting algorithms by David R. Martin and various Java applets by many college or university staff.

However, one of the most intriguing demos of integer sorting algorithms is the visualization and "audibilization" by andrut, available in a YouTube video. However, there is not a whole lot of technical information available about how sound is generated from the sorting algorithms' operations. According to the YouTube comment, there have been two previous approaches to generating sound from sorting: first and second. Both are constrained by using MIDI notes and slow instruments. Andrut's is the first good sound generator, and it was the main guideline for the sound effects in the Sound of Sorting.

As was pointed out to me, Andrut's video is again not the first sound generator for sorting algorithms. The old QBasic produced by Microsoft in 1991 also contained a sorting demo program with audibilization: SORTDEMO.BAS, which can be viewed on YouTube. So one sees again, no idea is really new, there is nothing new under the sun. [Added 2013-10-25]

However, for use in undergraduate teaching the YouTube demo has a lot of drawbacks. Most importantly, it cannot be slowed down! It also contains little additional information about how the algorithms operate. Furthermore, the set of algorithms is very small and some are not as good as they could be. Thus I decided to create my own for the algorithms course we were teaching in Karlsruhe in 2013.



Categorías