Die meisten Visualisierungen zu Sortieralgorithmen sind animiert. Dabei können die Funktionsweisen der Algorithmen dargestellt werden, wenn die Reihenfolge der Elemente auf einer und die Sortierschritte auf der anderen Achse abgebildet werden. Die untenstehenden Darstellungen zeigen statische Abbildungen, die den Sortiervorgang verdeutlichen.
Die Inspiration hierfür stammt von diesen Visualisierungen bekannter Sortieralgorithmen mit der Cairo-Bibliothek. Die untenstehenden Visualisierungen sind in D3 implementiert. Später entdeckte ich eine Implementierung auf Observable, die mich inspirierte, die Wahl der Farben zu verbessern. Auf Observable finden sich auch Algorithmen zum Mischen und eine animierte Version. Können Sie die Abbildungen den klassischen Sortieralgorithmen zuordnen?
Bei Insertionsort werden die Elemente der Liste nacheinander durchlaufen. Auf diese Weise wird eine sortierte Teilliste konstruiert, indem Elemente an die richtige Stelle der Teilliste verschoben werden.
Mergesort ist ein rekursiver Algorithmus, bei dem schrittweise Teillisten zusammengefügt und dabei sortiert werden. Die Abbildung zeigt beispielsweise, dass die beiden Teillisten vor dem letzten Schritt bereits jeweils farblich korrekt sortiert sind.
Heapsort ist ein Sortieralgorithmus, der einen Heap als Datenstruktur verwendet, eine besondere Form eines Baums. Bei einem Max-Heap sind die Elternknoten größer als die Kindknoten. So lässt sich das größte Element des verbleibenden Baums finden und der sortierten Teilliste hinzufügen. Die Abbildung zeigt die zwei Schritte: die Sortierung des Baums und die Extraktion des größten Elements, erkennbar an dem Sprung, den alle Elemente von oben nach unten machen.
Quicksort ist ein rekursiver Sortieralgorithmus, bei dem in jedem Schritt ein Pivotelement gewählt, um die Liste in zwei Teillisten zu unterteilen. Die Elemente werden in die beiden Teillisten verschoben, sodass alle Elemente der einen Teilliste nicht größer und alle der anderen nicht kleiner als das Pivotelement sind. Die Abbildung zeigt, dass die Elemente durch die Rekursion schrittweise an ihre richtigen Positionen gelangen.
Selectionsort funktioniert ähnlich wie Insertionsort, indem die Liste durchlaufen und iterativ eine sortierte Teilliste konstruiert wird. Bei Selectionsort wird das kleinste (verbleibende) Element der Liste gesucht, um es an die sortierte Teilliste anzuhängen.