Sortieralgorithmen animiert und im Detail
Jeder der irgendwie was mit Informatik zu tun hat ist schon einmal drauf gestoßen oder durfte sich mehr oder weniger freiwillig damit beschäftigen: Sortieralgorithmen. Meinereins musste sie zum Beispiel im Studium in C nachprogrammieren und es wurde diesem Thema sogar eine ganze Vorlesung gewidmet. Darin kamen dann Namen wie Bubblesort, Mergesort oder Quicksort auf oder man musste irgendetwas von einer Komplexität O(n) erzählen bzw errechnen.
Wer zu diesem Thema eine wirklich brauchbare Lernhilfe (auch zum wiederholen geeignet ;)) benötigt sollte sich mal die “Animated Sorting Algorithm Demo” von David Martin, Assistent an der Boston University für Informatik, ansehen.
Man kann auf dieser Seite die Sortieralgorithmen live gegeneinander “antreten” lassen und beobachten. Dabei sind die grauen Balken die unsortierten Werte, die schwarzen sind bereits sortiert und der rote Pfeil zeigt die aktuelle Position des Algorithmus. Man kann zwischen einer Sortiermenge von 20 bis 50 Elementen wählen und bekommt animiert gezeigt wie die Algorithmen funktionieren. Die Animiation startet man mit dem grünen Pfeil. Neben der typischen vermischten Wertemenge ist eine “Best-Case” (bereits sortiert), “Worst-Case” (umgekehrt sortiert) und mehrere doppeltet Einträge als Animation vorhanden.
Neben der Übersicht ist es möglich jeden einzelnen der aufgelisteten Sortieralgorithmen im Detail anzuschauen. Insgesamt werden acht Algorithmen verglichen und erläutert:
Sieht man sich die Detailseite eines Algorithmuses an bekommt man diesen im Detail erläutert und kann eine Animation dazu ansehen. Hier im folgenden zum Beispiel der Mergesort.
Die Animation selbst zeigt wieder alle vier Szenarien der Wertemenge:
Der Algorithmus selbst:
m = n / 2 sort a[1..m] recursively sort a[m+1..n] recursively copy a[m+1..n] to temp space merge
Dann noch die Eigenschaften:
- Stable
- O(n) extra space (see below)
- Ω(n·lg(n)) time
- Completely non-adaptive
Und zum Schluss noch einen Text mit Erklärungen zu den Vor- oder Nachteilen dieses Algorithmuses.
David Martin hat als Referenzen die Bücher Algorithms in Java 1-4 (Robert Sedgewick) und Programming Pearls (Jon Bently) angegeben.
 |
 |
Für das Buch Programming Pearls wurden die verschiedenen Sortieralgorithmen ebenfalls programmiert und sind aber, im Gegensatz zu dem oben vorgestellten Animationen, als Java Applet im Browser zu sehen. Aber die Darstellung des arbeitenden Algorithmus ist etwas anders, so dass man die etwas Ladezeit des Applets in Kauf nehmen sollte um auch dort mal einen Blick drauf zu werfen.
Insgesamt eine wirklich sehr gelungene Darstellung und Erläuterung von Sortieralgorithmen. Man erhält auf ein eine schnelle und einfache Art und Weise einen kleinen Einblick in die Welt der Sortierung. Schon allein deswegen ist die “Animated Sorting Algorithm Demo” Seite von David Martin ein Bookmark wert.
Wenn du Fragen oder Anregungen zum Post hast, dann hinterlasse doch einen Kommentar oder wenn du weiterhin Artikel von Javathreads lesen möchtest, dann abonniere den RSS Feed und sehe direkt in deinem Feed Reader die nächsten Artikel.
Ich find das richtig geil mit den Bubbles und so. Dass das überhaupt so bubblig sortiert, übelst krass. RESPEKT an Professor Doktor Konrad Bubble, der das erfunden hat.