Sortieralgorithmen eignen sich sehr gut für Laufzeit- und Speichernutzungsabschätzungen und sind somit essentiell für den Themenbereich “Datenstrukturen und Algorithmen“ der Informatik. Aufgrund ihrer Arbeitsweise (Feldzugriffe, Schleifen, Rekursionen, Parallelisierbarkeit, …) eignen sie sich auch sehr gut zum Erlernen einer neuen Programmiersprache und besitzen somit auch hohe Bedeutung in der Praxis. Und ganz nebenbei kommen die Algorithmen auch tatsächlich beim Sortieren von Daten zum Einsatz.

Aufgrund dieser theoretischen und praktischen Bedeutung ist ein vollständiges Verständnis der Funktionsweise der Algorithmen besonders wichtig. Dieses Verständnis kann durch geeignete Visualisierungen sehr stark gefördert werden, weshalb wir im Folgenden kurz auf die verschiedenen Formen der Visualisierung eingehen wollen:

Handelt es sich um ein In-Place-Sortierverfahren, also ein Sortierverfahren, das ohne zusätzlichen Speicher auskommt und erfolgt die Sortierung innerhalb einer Felddatenstruktur, so besteht die einfachste Form der Visualisierung in der Darstellung der Feldinhalte. Die Position repräsentiert den Feldindex (hier: 0..9). Der Wert den Feldinhalt (hier: 0..9):

4

8

1

9

5

6

0

3

7

2

Es handelt sich dabei um einen Snapshot zu einem bestimmten Zeitpunkt. Vertauschungen/Veränderungen können direkt visualisiert werden, Indexpositionen (bei Schleifen) können durch Einfärbungen sichtbar gemacht werden und es ist sogar möglich parallel zur Visualisierung den Quellcode quasi im Debugging-Modus darzustellen und auszuführen.

Solidware: Sort Animation

Nimmt man alle Snapshots der zuvor beschriebenen Visualisierung und reiht diese untereinander auf, so erhält man ein Index-Time-Diagramm. Der gesamte Ablauf ist vollständig visualisiert. Die Nachverfolgung von Werten oder Indexpositionen ist problemlos möglich.

Die Darstellungen “Feldinhalte” und “Blick von oben” sind leider nur für eine kleine Anzahl von Werten sinnvoll. Es besteht jedoch die Möglichkeit die Werte nicht nur inhaltlich anzuzeigen, sondern auch farblich zu visualisieren. So können kleine Werte dunkel und große Werte hell dargestellt werden. Werden nun die Feldinhalte ganz weg gelassen und nur noch durch unterschiedlich helle Pixel visualisiert, so ist eine deutliche Erhöhung der Wertemenge möglich.

Michael Kreil: Sortieralgorithmen von innen

Kehren wir wieder zurück zur Visualisierung “Feldinhalte” und nutzen die bisher ungenutzte Y-Koordinate zur Visualisierung des Feldinhaltes. Die Feldinhalte werden also nicht mehr nur durch einen Wert, sondern zusätzlich durch einen unterschiedlich hohen Balken visualisiert. Dieses Index-Value-Balkendiagramm besitzt die gleichen Vor- und Nachteile, wie die zugrunde liegende Visualisierung “Feldinhalte”, aber eine höhere Anschaulichkeit.

Die Darstellung ist ebenfalls nur für eine kleine Anzahl von Werten sinnvoll. Es ist jedoch möglich den Feldwert durch einen einzelnen Pixel darzustellen, welcher die obere Spitze des Balkens repräsentiert. Die Darstellung des Balkens und des Feldinhaltes ist nicht mehr zwingend notwendig, wodurch eine deutliche Erhöhung der Datenmenge möglich ist. Im Gegensatz zur Visualisierung "Blick von oben” sind auf diese Weise sogar Datenmengen visualisierbar, die größer sind als das Diagramm in der Breite an Pixel nutzen kann, da es unkritisch ist, wenn in einer Spalte mehrere Pixel auftauchen.

Die Visualisierung einzelner Vertauschungen oder das parallele Debuggen des Sortierverfahrens ist bei einer größeren Datenmenge nicht mehr sinnvoll. Eine Markierung der Indexpositionen ist jedoch noch machbar. Es besteht auch die Möglichkeit die Pixel einzufärben (Helligkeit), wenn diese sich ihrer Zielposition nähern, ihre Ausgangsposition verlassen bzw. ihre Zielposition erreicht haben (=Status). Um den Snapshoteffekt etwas abzumildern, ist zudem die Realisierung eines Memoryeffektes denkbar, d.h. die Pixel werden bei Vertauschungen auf dem Bildschirm nicht sofort gelöscht, sondern verblassen langsam.

Jason: Harrison: Sorting Algorithms
xSortLab Lab: Sorting and the Analysis of Algorithms
Peter Weigel: Sortieralgorithmen (VASA/VESA)

Nun werden Sie sich sicherlich fragen, wieso denn die beiden letztgenannten Visualisierungen von mir “Blick von oben” und “Blick von vorn” genannt werden. Grund ist die Tatsache, dass die beiden Darstellungen lediglich spezielle Projektionen einer 3D-Visualisierung sind:

Das Verfahren eines mit einer Felddatenstruktur arbeitenden In-Place-Sortieralgorithmen wird durch die Parameter Index, Time und Value eindeutig charakterisiert. Sind zwei Parameter bekannt, ist der dritte wohldefiniert und berechenbar. Eine vollständige Visualisierung erhält man daher durch dreidimensionale Darstellung dieser drei Parameter (X = Index, Y = Time, Z = Value) bei gegebener Wertemenge und gegebenem Sortierverfahren. Die vierte Dimension “Objekteigenschaft“, also die Farbe, die Helligkeit, die Form oder der Inhalt des Pixels, kann dann zur redundanten Visualisierung ausgewählter Informationen (z.B. Value bei “Blick von oben“, oder Time bei “Blick von vorn“ mit Memoryeffekt) oder zur Darstellung von Zusatzinformationen (Indexposition, Nähe zur Zielposition, Status) genutzt werden.

Bei “Blick von oben” wird von oben auf den dreidimensionalen Würfel geschaut. Bei “Blick von vorn” dagegen von vorn (wobei der Würfel hier aufgeschnitten werden muss, damit man auch etwas sieht, oder aber es wird sehr stark von dem Memoryeffekt gebrauch gemacht). Somit sind diese Visualisierungen lediglich spezielle Projektionen der hier beschriebenen 3D-Visualisierung. Die 3D-Visualisierung macht allerdings die Projektionen nicht überflüssig. Da “Blick von oben” und “Blick von vorn” die vierte Dimension auf unterschiedliche unvereinbare Weise nutzen, ist eine vollständige Integration in die dreidimensionale Darstellung nicht möglich, oder aber diese würde sehr farbig werden (Helligkeit = Value, Farbe = Time) und damit ggf. an Anschaulichkeit verlieren.

Die zuvor beschriebene dreidimensionale Darstellung offenbart uns eine weitere Projektion, die interessante Einblicke in die Arbeitsweise eines Sortieralgorithmus liefern kann - der Blick von der Seite. Hierbei erfolgt eine Visualisierung als Time-Value-Diagramm. Die Darstellung ist ähnlich dem “Blick von oben”, jedoch ist der Inhalt nicht der Wert, sondern der Index. Mithilfe der Helligkeit kann der Index zusätzlich visualisiert werden. Die Markierung der Indexpositionen bei Schleifendurchläufen macht in dieser Darstellung keinen Sinn. Außerdem ist die Darstellung nur möglich, wenn jeder Wert nur einmal vorkommt und zu jedem Zeitpunkt somit eine eindeutige Zuordnung zwischen Index und Value möglich ist.

Mit den zuvor beschriebenen Varianten sollten sämtliche möglichen Visualisierungen von In-Place-Sortierverfahren abgehandelt sein. Natürlich sind, wie ja bereits angedeutet, verschiedenste Abwandlungen möglich, diese lassen sich aber stets auf die hier beschriebenen Varianten reduzieren.

Für Out-of-Place-Sortierverfahren ist eine solche Kategorisierung von Visualisierungen nicht möglich. Die Visualisierung eines Out-of-Place-Sortierverfahrens ist speziell auf die Strukturen des Verfahrens zugeschnitten und somit einzigartig. Leider ist die Visualisierung somit auch nicht auf andere Algorithmen übertragbar und sehr aufwendig in der Realisierung.

Die auf dieser Internetpräsenz vorgestellten Sortierverfahren B-Sort und AVL-Sort sind sehr kompliziert und kaum verständlich zu vermitteln. Beide Verfahren basierten auf komplexen Algorithmen zur Erzeugung sortierter ausgewogener Baumstrukturen. Erst am Ende erfolgt die Umsortierung der Elemente in der zugrunde liegenden Feldliste. Eine Visualisierung dieser Baumstrukturen würde das Verständnis für die Arbeitsweise der beiden Algorithmen sehr stark erhöhen…

Die Palette der heute bekannten und auch genutzten Sortieralgorithmen ist riesig. Trotzdem kann man auch mal versuchen selber welche zu entwickeln.

Bevor Sie bei der großen Menge an Inspirationen auf die Idee kommen sollten, selbst mal einen Sortieralgorithmus zu entwerfen, sollten Sie jedoch wissen, dass kein allgemeines Sortierverfahren im worst-case besser als Ω(nlogn) sortieren kann! Und im best-case geht es auch niemals besser als Ω(n)! Bei Parallelrechnern kann der worst-case/best-case maximal auf Ω(logn) reduziert werden. Sie sollten aber noch einige andere Dinge beachten. Ein Algorithmus sollte wenig Speicher benötigen. Daher ist es immer gut, wenn er iterativ und in-place realisiert werden kann. Stabilität wäre auch nicht verkehrt. Er sollte auch für Listen einsetzbar sein, um ein größtmögliches Einsatzgebiet zu garantieren. Die Laufzeit sollte immer zwischen Ω(logn) bis Ο(n²) liegen. Außerdem sollten so wenig Bedingungen wie möglich an die Elemente geknüpft werden (also z.B. Feldgröße muss eine Zweierpotenz sein oder zwei Elemente sind immer ungleich ist sehr unschön). Und das wichtigste, er sollte funktionieren.

Ich selber habe natürlich auch ein bisschen herumexperimentiert. In wieweit die neu entwickelten Algorithmen oder Varianten von bereits existierenden Algorithmen bereits bekannt sind, weiß ich nicht. Aber so lange nicht das Gegenteil bewiesen ist, behaupte ich mal, dass ich der erste bin, der diese "genialen" Ideen hatte.

Es gibt mehrere Methoden zur Entwicklung neuer Algorithmen. Zum einen könnte man einen bereits existierenden Algorithmus nehmen und diesen dann vereinfachen (siehe z.B. Insertsort), verbessern (siehe z.B. Shakersort) oder parallelisieren (siehe z.B. Bubblesort, Simplesort, Combsort). Außerdem könnte man durch Veränderungen völlig neue Algorithmen oder Varianten konstruieren (siehe z.B. Jumpsort, "Listen-Optimierung"-Varianten bei Bubblesort, Selectsort, Simplesort, ...). Eine weitere Methode ist die Suche des Optimums bei parametrisierbaren Algorithmen (siehe z.B. Shellsort, Combsort, Heapsort). Am Interessantesten sind natürlich völlig neue Algorithmen (siehe z.B. Plaselsort, Partitsort, Avlsort, Tepifsort).

Peter Weigel: Sortieralgorithmen