Die folgenden Beispielprogramme erlauben das Testen von unterschiedlichen Sortieralgorithmen.

Hinweis: Die Implementierungen der Sortieralgorithmen selbst sind in den Abschnitten der Algorithmen zu finden. Im Hauptprogramm MainSort kann man durch Instanziieren einen Sortieralgorithmus wählen.

Arbeitsanweisung

Kopieren, Bauen und Starten der Referenzimplementierung

1. Legen Sie in Ihrer Entwicklungsumgebung das Paket s2.sort an
2. Kopieren Sie die Quellen der unten aufgeführten Klassen (inklusive Trivialsort) in Ihre Entwicklungsumgebung. Achten Sie darauf, daß alle Klassen im Paket s2.sort angelegt werden.
3. Übersetzen Sie alle Klassen
4. Starten Sie Anwendung durch Aufruf der Klasse s2.sort.MainSort

Auf der Kommandozeile geschieht das mit dem Befehl

$ java s2.sort.MainSort

Die Konsolenausgabe dieser Anwendung ist:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortiere drei Werte
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
 Zeit(ms): 0 Vergleiche: 2 Vertauschungen: 2. Fehler in Sortierung
Sortiert:
feld[0]=2
feld[1]=4
feld[2]=6
feld[3]=3
feld[4]=5
feld[5]=7
Keine Phase 2 (Stresstest) aufgrund von Fehlern...

Der Trivialsort hat leider nur die Schlüssel auf der Position 0 und 1 sortiert.

Effizienz des Algorithmus messen

Das Hauptprogramm MainSort wird bei einer korrekten Sortierung eines Testfelds mit 6 Werten automatisch in die zweite Phase eintreten.

Hier wird es ein Feld mit 5 Werten und Zufallsbelegungen Generieren und Sortieren.

Die Feldgröße wird dann automatisch verdoppelt und es wird eine neue Sortierung mit neuen Zufallswerten durchgeführt. Dies wird solange wiederholt bis ein Sortiervorgang eine voreingestellte Maximalzeit (3 Sekunden) überschritten hat.

Mit Hilfe dieser Variante kann man die benötigte Zeit pro Anzahl sortierter Elemente beobachten und die Effizienz des gewählten Algorithmus abschätzen.

Beim Sortieren durch Auswahl ergibt die die folgende Konsolenausgabe:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortieren durch Auswahl
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
 Zeit(ms): 0 Vergleiche: 15 Vertauschungen: 5. Korrekt sortiert
Sortiert:
feld[0]=2
feld[1]=3
feld[2]=4
feld[3]=5
feld[4]=6
feld[5]=7
Phase 2: Stresstest
Der Stresstest wird beendet nachdem mehr als 3 Sekunden benötigt werden.
Maximalzeit(s): 3
Sortieren durch Auswahl. Feldgroesse: 10 Zeit(ms): 0 Vergleiche: 45 Vertauschungen: 9. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 20 Zeit(ms): 0 Vergleiche: 190 Vertauschungen: 19. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 40 Zeit(ms): 0 Vergleiche: 780 Vertauschungen: 39. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 80 Zeit(ms): 1 Vergleiche: 3160 Vertauschungen: 79. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 160 Zeit(ms): 5 Vergleiche: 12720 Vertauschungen: 159. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 320 Zeit(ms): 14 Vergleiche: 51040 Vertauschungen: 319. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 640 Zeit(ms): 14 Vergleiche: 204480 Vertauschungen: 639. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 1280 Zeit(ms): 19 Vergleiche: 818560 Vertauschungen: 1279. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 2560 Zeit(ms): 26 Vergleiche: 3275520 Vertauschungen: 2559. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 5120 Zeit(ms): 84 Vergleiche: 13104640 Vertauschungen: 5119. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 10240 Zeit(ms): 575 Vergleiche: 52423680 Vertauschungen: 10239. Korrekt sortiert
Sortieren durch Auswahl. Feldgroesse: 20480 Zeit(ms): 1814 Vergleiche: 209704960 Vertauschungen: 20479. Korrekt sortiert

Warnung

• Diese zweite Phase funktioniert nicht mit dem Trivialsort. Hier werden nur zwei Vergleiche und zwei Vertauschnungen durchgeführtImplementieren der eigenen Algorithmen

 Nutzen Sie die vorgebenen Klassen zum Testender  eigener Algorithmen

• Erzeugen Sie eine eigene Klasse für den Sortieralgorithmus
  • Sie können die Klasse TrivialSort übernehmen.
    • Ändern Sie den Klassennamen
    • Ändern Sie in der Methode algorithmus() den Namen des Algorithmus
    • Implementieren Sie die Methode sortieren(int von, int bis) die ein bestimmtes Intervall der Folge sortiert
• Ändern Sie in der Klasse MainSort in der Methode algorithmusWahl() den benutzten Algorithmus.
• Tipps: Nutzen Sie die Infrastruktur der Oberklasse Sortierer beim Testen
  • istKleiner(int a, int b), istKleinerGleich(int a, int b) : Vergleichen Sie die Werte des Feldes indem Sie bei diesen beiden Methoden den jeweiligen Index angeben. Es wird ein Zähler gepflegt der die Anzahl der gesamten Vergleiche beim Sortiervorgang zählt!
  • tausche(int i, int j): tauscht die Werte auf Index i mit dem Wert von Index j. Es wird ein Zähler gepflegt der die Anzahl der Vertauschungen zählt
  • tZaehler(): Inkrementiert die Anzahl der Vertauschungen falls nicht die Methode tausche() verwendet wurde. Dieser Zähler ist multi-threading (mt) save!
  • vglZaehler(): Inkrementiert die Anzahl der Vergleiche falls nicht die Methoden istKleiner() oder istKleinerGleich() verwendet werden. Dieser Zähler ist mt-save!
  • druckenKonsole() : druckt das Feld in seiner aktuellen Sortierung aus.
  • Tracing: Ihre Klasse mit dem Sortieralgorithmus erbt eine statische boolsche Variable geschwaetzig. Sie können diese Variable jederzeit setzem mit geschwaetzig=true. Es werden alle Vertauschungen und Vergleiche auf der Konsole ausgegeben:

Beim TrivialSort führt das Setzen dieser Variable zur folgenden Konsolenausgabe:

Phase 1: Einfacher Test mit 6 Elementen
Algorithmus: Sortiere drei Werte
Unsortiert:
feld[0]=6
feld[1]=2
feld[2]=4
feld[3]=3
feld[4]=5
feld[5]=7
Vergleich:feld[1]<feld[0] bzw. 2<6
Getauscht:feld[0<->1];f[0]=2;feld[1]=6
Vergleich:feld[2]<feld[1] bzw. 4<6
Getauscht:feld[1<->2];f[1]=4;feld[2]=6
 Zeit(ms): 0 Vergleiche: 2 Vertauschungen: 2. Fehler in Sortierung
Sortiert:
feld[0]=2
feld[1]=4
feld[2]=6
feld[3]=3
feld[4]=5
feld[5]=7
Keine Phase 2 (Stresstest) aufgrund von Fehlern...

Quellcode

Klasse MainSort.java

Warnung: Diese Klasse lädt die Algorithmen dynamisch. Sie funktioniert nur wenn

• Die Namen der Klassen beibehalten werden. Die Namen der Klassen werden als Zeichenkette angegeben. Die Namen müssen vorhanden sein und die Klasse muss übersetzt worden sein.
• Das Paket s2.sort bleibt. Wenn die Paketstruktur geändert wird muss auch die fett gedruckte Zeichenkette angepasst werden.

Die Klasse MainSort.java in GitHub.

Klasse Sortieren.java

 Die Klasse Sortierer ist eine abstrakte Klasse die die Infrastruktur zum Sortieren zur Verfügung stellt.

• Sie verwaltet ein Feld von ganzen Zahlen (int).
• Sie stellt Operationen zum Vergleichen und Tauschen von Elementen zur Verfügung
• Sie hat Zähler für durchgeführte Vertauschungen
• Sie kann ein Feld auf korrekte Sortierung prüfen
• Sie kann das Feld mit neuen Zufallszahlen belegen
• Sie hat eine statische Variable geschwaetzig mit der man bei Bedarf jeden Vergleich und jede Vertauschung auf der Kommandozeile dokumentieren kann.
• Die Klasse verwendete mt-sichere Zähler vom Typ AtomicInteger bei parallelen Algorithmen. Diese Zähler sind langsamer aber Sie garantieren ein atomares Inkrement.

Die Klasse Sortierer.java in GitHub.

Die Klasse TrivialSort.java

Diese Klasse ist ein Platzhalter der nur die beiden ersten Elemente eines Intervalls sortieren kann.

Das Programm dient zum Testen des Beispiels und es zeigt den Einsatz der schon implementierten istKleiner() und tausche() Methoden die von der Oberklasse geerbt werden.

Die Klasse TrivialSort.java in GitHub.