Sortieralgorithmen von innen als neu markieren
(Dienstag, 22.05.2007 01:27)
Die folgende Visualisierung von Sortieralgorithmen waren schon auf meiner alten Webseite zu sehen und sind (glaub' ich) aus dem Jahre 2000. Weil Sie aber so hübsch anzusehen sind, präsentiere ich sie hier noch einmal.
Die Algorithmen (BubbleSort, InsertSort, JumpSort, MergeSort, MinSort, QuickSort, RadixSort und ShellSort) habe ich alle noch einmal implementiert. Einziger Unterschied: Nach jedem Rechenschritt wird die aktuelle (teilweise sortierte) Zahlenfolge als Grauverlauf gespeichert. Raus kommen die folgenden merkwürdigen Darstellungen, die aber einen interessanten Einblick in die Funktionsweise von Sortieralgorithmen geben.
In der folgenden Tabelle sind die Visualisierungen der unterschiedlichen Sortieralgorithmen aufgelistet. Die y-Achse der Bilder entspricht (von oben nach unten) dem Fortschritt der Sortierung und ist in etwa proportional zur Zeit.
Zeilenweise sind die entsprechenden Zahlenfolgen im aktuellen Rechenschritt als Grauwerte gezeichnet, dabei steht schwarz für die kleinste und weiß für die größte Zahl. So kann man den Verlauf der Sortierung genau beobachten.
| Sortieralgorithmus | Art der Zahlenfolge | ||||
| rückwärts sortiert |
rückwärts verrauscht |
vorwärts sortiert |
vorwärts verrauscht |
zufällig | |
| BubbleSort Der rote Bereich entspricht der inneren Schleife. |
 |
 |
 |
 |
 |
| InsertSort Der rote Bereich entspricht der inneren Schleife. |
 |
 |
 |
 |
 |
| JumpSort Der rote Bereich entspricht der inneren Schleife. |
 |
 |
 |
 |
 |
| MergeSort Im roten Bereich wird zusammengefügt. |
 |
 |
 |
 |
 |
| MinSort Der rote Bereich entspricht der inneren Schleife. |
 |
 |
 |
 |
 |
| QuickSort Im roten Bereich wird um das Pivotelement sortiert. |
 |
 |
 |
 |
 |
| RadixSort Der rote Bereich entspricht der inneren Sortierung. |
 |
 |
 |
 |
 |
| ShellSort |  |
 |
 |
 |
 |
Einige Implementierungen der Sortieralgorithmen stammen von www.sortieralgorithmen.de.