Im Rahmen einer Projektarbeit der Veranstaltung "Praxis des Programmierens" im 3. Fachsemester (Wintersemester 2000/2001) des Studienganges Diplom-Informatik an der Martin-Luther-Universität Halle-Wittenberg haben wir, Andreas Brotzmann und ich, uns mit der Darstellung/Visualisierung der Funktionsweise von Sortieralgorithmen beschäftigt. Dabei sind einige interessante Komponenten/Objekte entstanden, die auch sehr gut in anderen Projekten eingesetzt werden können. Das Ergebnis (den Java-Quellcode) können Sie hier herunterladen. Die Visualisierung ist direkt auf dieser Homepage als Java-Applet verfügbar.

Um Elemente überhaupt sortieren zu können, benötigt man eine einfache und flexible Datenstruktur, die entweder ein Feld oder eine Liste realisiert. Sie sollte gut erweiterbar und auf alle üblichen Datentypen anwendbar sein.

Zu diesem Zweck haben wir eine Schnittstellendefinition (ifield) geschaffen die alles enthält, was ein Sortieralgorithmus wissen muss. Diese Definition wurde dann für jeden Datentyp (int, float, ...) noch etwas erweitert (iintfield, ifloatfield, ...). Um das Prinzip von Schnittstellen zu verdeutlichen, wurden zwei verschiedene Implementierungen von iintfield realisiert. Die Dateien dieses Teilgebietes bestehen also aus Interfaces (ielement, ifield, ibytefield, ishortfield, iintfield, ifloatfield, idoublefield, icharfield, istringfield) und Klassen (bytefield, shortfield, intfield, integerfield, floatfield, doublefield, charfield, stringfield).

Die Elemente der oben genannten Datenstruktur müssen nun sortiert werden. Dafür benötigen wir Sortieralgorithmen, die alle die selbe Schnittstelle besitzen sollten.

Zu diesem Zweck haben wir erst ein Interface für alle Sortieralgorithmen geschaffen (isort) und dann die jeweiligen Algorithmen implementiert (trippelsort, bubblesort, shakersort, ripplesort, oetsort, selectsort, naiselsort, jumpsort, plaselsort, partitsort, insertsort, shellsort, combsort, bitonicsort, quicksort, mergesort, heapsort, avlsort). Zusätzlich wurde die Klasse sortbucket eingeführt, die den Zugriff auf alle Algorithmen mittels Index oder String ermöglicht.

Die Ergebnisse aus den Teilaufgaben 1 und 2 sind ausreichend zum Sortieren von beliebigen Elementen und können daher in jedem Programm angewendet werden. Teilaufgabe 3 und 4 sind dazu nicht erforderlich.

Der kompletten Java-Quellcode stehen Ihnen im Downloadbereich zum Herunterladen zur Verfügung.

Die dritte Teilaufgabe, die Visualisierung aller allgemeinen Sortieralgorithmen, war natürlich unser Schwerpunkt. Eine genauere Funktionserläuterung ist hier überflüssig, da das Ergebnis selbsterklärend ist. Diese Anwendung ist sowohl als Applet als auch als normale Java-Anwendung ausführbar.

Neben den direkt zu diesem Teilgebiet gehörenden Dateien (vasaapplet, vasa, AboutBox, BorderPanel, ControlPanel, GroupBox, TimeLabel, ptele und ptfield) wird auch ein Teil von pefas benötigt.

Auch diese Dateien stehen Ihnen im Downloadbereich zum Herunterladen zur Verfügung (pefas ist in gekürzter Fassung enthalten).

Die vierte Teilaufgabe, die Visualisierung einzelner Sortieralgorithmen, ist eine Erweiterung speziell für diese Internetpräsenz und gehörte nicht zum Projektumfang. Die Steuerung erfolgt ausschließlich über Parameter und die Maus (linke und rechte Maustaste). Der Algorithmus, die Feldgröße und die Verzögerungsrate müssen per Parameter angegeben werden. Die Feldinitialisierung (Zufällig oder Absteigend) erfolgt mit der rechten Maustaste. Das Starten und vorzeitige Stoppen des Sortiervorganges wird durch die linke Maustaste gesteuert.

Diese Teilaufgabe besteht aus genau einer zusätzlichen Datei (vesaapplet) und ist in vasa enthalten.

pefas - Package of Efficient Fields and Algorithms for Sorting
vasa - Visualisierung allgemeiner Sortieralgorithmen
vesa - Visualisierung einzelner Sortieralgorithmen

Die Anwendungen VASA, VESA und das Package PEFAS können (gegen eine kleine Aufwandsentschädigung) im Downloadbereich heruntergeladen und ohne Einschränkung angewendet werden. Nutzung und Weiterentwicklung sind ausdrücklich erwünscht. Änderungen am Quellcode müssen explizit gekennzeichnet werden. Die Urheberechte liegen bei Peter Weigel und Andreas Brotzmann. Auch bei veränderten Versionen muss das noch erkennbar sein.