3. Wie die Algorithmen entstehen

Unter Algorithmen stehen inzwischen vier Visualisierungen: binäre Suche, Selectionsort, Insertionsort und Shellsort. So entstehen sie.

Was ich bekomme

Von dir kommen zwei Dinge: ein Foto des Listings aus dem Sedgewick und ein Erklärtext der Instanz „Algo“. Den Text übernehme ich Wort für Wort. Das Listing schreibe ich nicht ab, sondern baue eine eigene Java-Fassung im selben Stil: int[] statt Comparable, deutsche Namen (sortiere, tausche), die Kommentare in eigenen Worten. Erstens ist der Buchcode urheberrechtlich geschützt. Zweitens passt die Fassung mit int[] besser zu den Zahlenbalken.

Das Grundprinzip: erst rechnen, dann blättern

Jede Visualisierung arbeitet in zwei Phasen:

1. Aufzeichnen. Der Algorithmus läuft einmal komplett durch, in ganz normalem JavaScript. An jeder interessanten Stelle hält er eine Momentaufnahme fest: das Array, die gerade ausgeführte Code-Zeile, einen Erklärsatz, die Zähler und die Markierungen (i, j, min …). Bei zwölf Zahlen sind das um die hundert Aufnahmen.
2. Abspielen. Die Anzeige blättert danach nur noch in dieser Liste. „Schritt“ heißt nächste Aufnahme, „Zurück“ heißt vorige Aufnahme, und „Bis Tausch“ blättert so lange weiter, bis eine Aufnahme mit Tausch kommt.

Für dich als Java-Entwickler: Das ist im Kleinen dasselbe wie Event Sourcing oder ein Debugger mit Aufzeichnung. Der Vorteil ist, dass die Anzeige selbst nichts rechnet und deshalb nicht falsch rechnen kann. „Zurück“ ist trivial, denn man muss keinen Algorithmus rückwärts laufen lassen. Und der Test liest genau dieselbe Liste, die du siehst.

Ein Rahmen, drei Verfahren

Die drei Sortierverfahren hatten anfangs je eine eigene Datei mit fast 300 Zeilen, und zwei Drittel davon waren in allen gleich: Knöpfe, Balken, Tempo, Protokolltabelle. Heute habe ich das umgebaut. Jetzt gibt es einen gemeinsamen Rahmen (sortieren/rahmen.js und rahmen.css), und jede Verfahrensdatei liefert nur noch ihren eigenen Teil:

• die Code-Zeilen für die Anzeige,
• baue(): den Algorithmus selbst mit den Momentaufnahmen,
• balken() und marken(): welche Farbe und Markierung ein Balken in einer Aufnahme bekommt,
• zaehler() und protokoll(): die Zählerzeile und die Tabelle wie im Buch.

Das ist das Muster Template Method: Der Rahmen ist die abstrakte Klasse, die den Ablauf festlegt, und jedes Verfahren füllt die Haken aus. Vorher waren es zusammen 891 Zeilen, jetzt 590, und ein Fehler in der Bedienung muss nur noch an einer Stelle behoben werden. Ein viertes Sortierverfahren braucht künftig nur noch gut hundert Zeilen.

Die binäre Suche ist bewusst nicht umgebaut: Sie sortiert nicht, sondern zeigt einen Aufrufstapel. Für sie würde der Rahmen nicht passen.

Gleiche Farben, gleiche Bedeutung

Damit man nicht bei jedem Verfahren neu lernen muss, bedeuten die Farben überall dasselbe: Orange ist das Element, um das es gerade geht (das Minimum, das einzufügende Element). Blau ist sein Vergleichspartner. Grün ist ein Tausch. Grau oder blass ist, was gerade keine Rolle spielt. Unter „Anordnung“ kann man ein schon sortiertes oder ein umgekehrtes Array wählen. Daran sieht man die Eigenschaften, über die der Erklärtext spricht: Selectionsort vergleicht immer gleich oft, Insertionsort ist bei sortierten Daten sofort fertig.

Testen: Das Buch ist der Schiedsrichter

Eine Animation, die gut aussieht, ist noch kein Beweis. Darum teste ich jedes Verfahren auf drei Arten automatisch im Browser:

1. Gegen eine Referenz. 300 zufällige Arrays, mit doppelten Werten und unterschiedlich lang, laufen durch die Visualisierung und durch eine zweite, unabhängig geschriebene Fassung desselben Algorithmus. Endergebnis, Zähler und jede Protokollzeile müssen übereinstimmen.
2. Gegen Gesetze. Was der Erklärtext behauptet, muss die Aufzeichnung zeigen: Selectionsort macht genau n(n−1)/2 Vergleiche und n Tausche, Insertionsort genau so viele Tausche, wie das Array Inversionen hatte, und am Ende darf keine Inversion übrig sein.
3. Gegen das Buch. Das Beispiel aus der Abbildung (SORTEXAMPLE, SHELLSORTEXAMPLE) geht als Buchstabenfolge hinein. Was herauskommt, muss Zeile für Zeile mit dem Foto übereinstimmen, bei Shellsort zum Beispiel PHELLSORTEXAMSLE nach dem 13er-Durchlauf.

Gefunden hat der Test vor allem die Stellen, die man in der Animation nicht sieht. Ein Beispiel: Kommt bei Insertionsort ein Element ganz vorn an, endet die Schleife über j > 0, ohne noch einmal zu vergleichen. Wer dort einen Vergleich zu viel zählt, bekommt im Bestfall n statt n−1 heraus. Solche Off-by-one-Fehler fallen nur auf, wenn ein Programm die Zahlen nachrechnet.

Nach dem Umbau zum gemeinsamen Rahmen sind alle drei Tests noch einmal gelaufen, mit denselben Ergebnissen wie vorher.

Was noch dazugehört

• Klein halten. 10 bis 20 Zahlen, das war deine Vorgabe. Es geht ums Verstehen, nicht um Tempo.
• Kein Fremdcode. Es werden keine Bibliotheken nachgeladen und keine Dienste aufgerufen. Alles läuft in deinem Browser.
• Einbettung. Die Visualisierung steckt in einem Rahmen (iframe) in der Seite, darunter stehen der Erklärtext und eine kurze Anmerkung von mir, wenn sich der Text auf Dinge im Buch bezieht, die in der Visualisierung anders heißen.
• Ein Fehler, den ich zweimal gemacht habe: das Datum einer neuen Seite in der Zukunft. Hugo blendet solche Seiten aus. Seitdem frage ich die Uhrzeit ab, bevor ich das Datum schreibe.