Skip to Content

Beispielprogramme

 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 Kurs2.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 Kurs2.Sort angelegt werden.
  3. Übersetzen Sie alle Klassen
  4. Starten Sie Anwendung durch Aufruf der Klasse Kurs2.Sort.MainSort

Auf der Kommandozeile geschieht das mit dem Befehl

$ java Kurs2.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 derm 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...

 

Comments

typo

[...]

Warnung

  • Diese zweite Phase funktioniert nicht mit derm Trivialsort. Hier werden nur zwei Vergleiche und zwei Vertauschnungen durchgeführt. (Absatz, dann Überschrift)

Implementieren der eigenen Algorithmen

[...]

Danke

wurde korrigiert



book | by Dr. Radut