Kreatives Video aus der Vorlesung “Algorithmen 1” erreicht enorme Reichweite auf YouTube

Sortieralgorithmen sind ein fester Bestandteil der Informatik Grundausbildung. Das Problem ist denkbar einfach: sortiere eine Menge von Objekten nach einer vorgegeben Ordnung. Die hierfür entwickelten Algorithmen sind sehr vielfältig und dennoch meist mit entsprechenden mathematischen Hilfsmitteln leicht zu analysieren. Diese Eigenschaften machen Sortieralgorithmen zu einer lehrreichen Einführung in die Mittel der theoretischen Informatik. Neben vielen alltäglichen Sortiervorgängen am Rechner werden diese Algorithmen auch in großem Maßstab in Datenbanken, Suchmaschinen und bei MapReduce-Verarbeitung von Big Data eingesetzt.

Die Theorie der verschiedenen Sortieralgorithmen erlernen die Studierenden der Informatik am Karlsruher Institut für Technologie (KIT) bereits im 2. Semester in der Vorlesung “Algorithmen 1”. Im Sommersemester 2013 wurde diese Veranstaltung von Professor Peter Sanders geleitet. Seine Mitarbeiter haben sich zur Visualisierung der Algorithmen mit dem Programm “The Sound of Sorting” eine besonders kreative Lösung einfallen lassen, die für großes Aufsehen in der Saalübung und weit darüber hinaus gesorgt hat.

Das Demo-Programm bestimmt experimentell die Anzahl der von den Algorithmen benötigten Vergleichsoperationen und stellt das zu sortierende Array graphisch dar. Darüber hinaus werden in Echtzeit "sound effects" erzeugt, deren Töne von den gerade verglichenen Zahlenwerten abhängen. Neben den Audioeffekten werden die verschiedenen Zählervariablen und Zustände der Algorithmen in der Visualisierung farblich hervorgehoben.

Das Ergebnis ist eine erstaunlich kunstvolle Darstellung von Algorithmik. Das mit dem Demo-Programm erzeugte Youtube-Video “15 Sorting Algorithms in 6 Minutes” stellt sich als hoch viral heraus und verteilte sich schnell in den einschlägigen sozialen Netzwerken. Bis heute wurde es bereits über 430.000 mal angesehen. (Stand vom 24.10.2013)

Und so funktionierts:
Die vom Algorithmus gerade bewegten oder gelesenen Array-Einträge werden rot markiert. Vergleicht der Algorithmus zwei Werte, so werden die beiden Zahlenwerte auf Frequenzen zwischen 120 Hz und 1.2 kHz umgerechnet und mit einer Dreiecksfunktion als Grundschwingung ausgegeben. Andersfarbig markierte Elemente dienen der Visualisierung von internen Zeigern oder Bereichen der Algorithmen. So wird beispielsweise bei Quicksort das aktuelle Pivotelement grün und die laufenden Zeiger blau hervorgehoben. Bei Selection Sort, Insertion Sort und ähnlichen wird der aktuell sortierte Teilbereich durch grüne Elemente abgegrenzt.  Die vielen Farben in der Visualiserung von Heapsort stellen die Ebenen des im Array aufgebauten binären Max-Heaps dar.

Screenshot aus dem Demo-Programm

Für Praktiker besonders interessant ist das Verhalten von std::sort, der Standardsortierfunktion von C++  und wahrscheinlich die am häufigsten eingesetzte Sortierroutine überhaupt. Zur Visualisierung von std::sort wurde die unveränderte Bibliotheksfunktion auf einem instrumentierten Array angewendet, dessen Iteratoren und Komparatoren die Operationen des Algorithmus verfolgen. Somit wird im “Sound of Sorting” das Vorgehen des Standardsortierers von C++ direkt angezeigt.

Einige der 15 Algorithmen wurden in der Saalübung am 22.5.2013 und am 29.5.2013 erklärt, die im KIT Informatik Youtube-Kanal zu sehen sind. Das Demo-Programm selbst wurde am 22.5. erstmals vorgestellt. Alle Erstsemester haben im kommenden Sommersemester 2014 wieder die Möglichkeit das Demo-Programm live und mit Erklärungen im Hörsaal zu erleben.

Vorlesung vom 22.5.2013: Selection-, Insertion-, Quick-, Merge-Sort, std::sort und std::stable_sort

Vorlesung vom 29.5.2013: Heap-Sort