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 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...

 

MainSort.java: Ein Testprogramm

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.
package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class MainSort { private static String algorithmusName;
/**
*
* Das Hauptprogramm sortiert sechs Zahlen in Phase 1
* Phase 2 wird nur aufgerufen wenn der Sortieralgorithmus
* für die erste Phase korrekt war
* @param args
*/
public static void main(String[] args) { if (args.length > 0)
algorithmusName = args[0];
else
algorithmusName="";
int zeit = 3;
System.out.println("Phase 1: Einfacher Test mit 6 Elementen");
boolean erfolg = phase1();
if (erfolg) {
System.out.println ("Phase 2: Stresstest");
System.out.print("Der Stresstest wird beendet nachdem mehr ");
System.out.println("als " + zeit + " Sekunden benötigt werden.");
phase2(zeit);
}
else {System.out.println("Keine Phase 2 (Stresstest) " +
"aufgrund von Fehlern...");}
}
/**
* Auswahl des Sortieralgorithmus
* @ param das zu sortierende Feld
* @ return der Sortieralgorithmus
*/
public static Sortierer algorithmusWahl(int[] feld) {
Sortierer sort= null;
// Wähle ein Sortieralgorithmus abhängig von der
// gewünschten Implementierung
String nameSortierKlasse;
if (algorithmusName.equals("")) {
algorithmusName = "TrivialSort";
//algorithmusName = "SelectionSort";
//algorithmusName = "InsertionSort";
//algorithmusName = "BubbleSort";
//algorithmusName = "QuickSort";
//algorithmusName = "QuickSortParallel";
}

Class<?> meineKlasse;
Constructor<?> konstruktor;

try {
// Dynamisches Aufrufen einer Klasse
// Hole Metainformation über Klasse
meineKlasse = Class.forName("s2.sort."+ algorithmusName);
// Hole alle Konstruktoren
Constructor[] konstruktoren = meineKlasse.getConstructors();
// Nimm den Ersten. Es sollte nure einen geben
konstruktor = konstruktoren[0];
// Erzeuge eine Instanz dynamisch
sort = (Sortierer) konstruktor.newInstance((Object)feld); } catch (ClassNotFoundException ex) { System.out.println("Klasse nicht gefunden. Scotty beam me up"); } catch (InstantiationException ex) { System.out.println("Probleme beim Instantieren. Scotty beam me up"); } catch (IllegalAccessException ex) { System.out.println("Probleme beim Zugriff. Scotty beam me up"); } catch (SecurityException ex) { System.out.println("Sicherheitsprobleme. Scotty beam me up"); } catch (IllegalArgumentException ex) { System.out.println("Falsches Argument. Scotty beam me up"); } catch (InvocationTargetException ex) { System.out.println("Falsches Ziel. Scotty beam me up"); } //sort.geschwaetzig = true; }

/**
* Sortiere 6 Zahlen
* @return wurde die Folge korrekt sortiert?
*/
public static boolean phase1() {
long anfangszeit = 0;
long t = 0;
int[] gz = new int[6];
gz[0] = 6;
gz[1] = 2;
gz[2] = 4;
gz[3] = 3;
gz[4] = 5;
gz[5] = 7;
Sortierer sort = algorithmusWahl(gz);
System.out.println("Algorithmus: " + sort.algorithmus());
System.out.println("Unsortiert:");
sort.druckenKonsole();
anfangszeit = System.nanoTime();
sort.sortieren(0, gz.length - 1);
t = System.nanoTime() - anfangszeit;
System.out.print(
" Zeit(ms): " + t / 1000000
+ " Vergleiche: " + sort.anzahlVergleiche()
+ " Vertauschungen: " + sort.anzahlVertauschungen());
boolean erfolg = sort.validierung();
if (erfolg) {System.out.println(". Korrekt sortiert");}
else {System.out.println(". Fehler in Sortierung");}
System.out.println("Sortiert:");
sort.druckenKonsole();
return erfolg;
}
/**
* Sortieren von zufallsgenerierten Feldern bis eine maximale
* Zeit pro Sortiervorgang in Sekunden erreicht ist
* @param maxTime
*/
public static void phase2(int maxTime) {
// Maximale Laufzeit in Nanosekunden
long maxTimeNano = (long) maxTime * 1000000000L;
long t = 0;
// Steigerungsfaktor für Anzahl der zu sortierenden Elemente
double steigerung = 2.0; // Faktor um dem das Feld vergrößert wird
int anzahl = 5; // Größe des initialen Felds
long anfangszeit;
int[] gz;
Sortierer sort;
System.out.println("Maximalzeit(s): " + maxTime);
while (t < maxTimeNano) {
// Sortiere bis das Zeitlimit erreicht ist
anzahl = (int) (anzahl * steigerung);
// Erzeugen eines neuen Feldes
gz = new int[anzahl];
for (int i = 0; i < gz.length; i++) {
gz[i] = 1;
}
sort = algorithmusWahl(gz);
sort.generiereZufallsbelegung();
sort.zaehlerRuecksetzen();
anfangszeit = System.nanoTime();
sort.sortieren(0, gz.length - 1);
t = System.nanoTime() - anfangszeit;
System.out.print(
sort.algorithmus() +
". Feldgroesse: " + anzahl + " Zeit(ms): " + t / 1000000 +
" Vergleiche: " + sort.anzahlVergleiche() +
" Vertauschungen: " + sort.anzahlVertauschungen());
if (sort.validierung()) {System.out.println(". Korrekt sortiert");}
else {System.out.println(". Fehler in Sortierung");}
sort.zaehlerRuecksetzen();
}
}
}

 Die Quellen bei github.

Sortierer.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.

Implementierung

package s2.sort;
import java.util.concurrent.atomic.AtomicInteger;
/**
*
* @author sschneid
* @version 2.1
*/
public abstract class Sortierer {
/**
* Das zu sortierende Feld
*/
protected int[] feld;
private int maxWert = Integer.MAX_VALUE;
// Zähler für serielle Sortieralgorithmen
private long tauschZaehlerSeriell;
private long vergleichszaehlerSeriell;
// Zähler für paralelle Sortieralgorithmen
private AtomicInteger tauschZaehlerParallel;
private AtomicInteger vergleichszaehlerParallel;
/**
* Der Algorithmus arbeitet parallel
*/
private final boolean parallel;
/**
* erweiterte Ausgaben beim Sortieren
*/
public static boolean geschwaetzig = false;
/**
* Initialisieren eines Sortierers mit einem
* unsortierten Eingabefeld s
* @param s ein unsortiertes Feld
* @param p der Algorithmus is parallel implementiert
*/
public Sortierer(int[] s, boolean p) {
feld = s;
parallel = p;
if (parallel) {
tauschZaehlerParallel = new AtomicInteger();
vergleichszaehlerParallel = new AtomicInteger();
}
else {
tauschZaehlerSeriell = 0;
vergleichszaehlerSeriell = 0;
}
}
/**
* die Groesse des zu sortierenden Feldes
*/
public int feldgroesse() {
return feld.length;
}
/**
* Gibt ein Feldelement auf gegebenem Index aus
* @param index
* @return
*/
public int getElement(int index) {
return feld[index];
}
/**
* sortiert das Eingabefeld
* @param s ein unsortiertes Feld
*/
abstract public void sortieren(int startIndex, int endeIndex);
/**
* Eine Referenz auf das Feld
* @return
*/
public int[] dasFeld() {
return feld;
}
/**
* kontrolliert ob ein Feld sortiert wurde
* @return
*/
public boolean validierung() {
boolean korrekt;
int i = 0;
while (((i + 1) < feld.length) &&
(feld[i]<=feld[i + 1])) {i++;}
korrekt = ((i + 1) == feld.length);
return korrekt;
}
/**
* Liefert den Namen des implementierten Sortieralgorithmus
* @return
*/
abstract public String algorithmus();
/**
* Drucken des Feldes auf System.out
*/
public void druckenKonsole() {
for (int i = 0; i < feld.length; i++) {
System.out.println("feld[" + i + "]=" + feld[i]);
}
}
/**
* Anzahl der Vertauschungen die zum Sortieren benoetigt wurden
* @return Anzahl der Vertauschungen
*/
public long anzahlVertauschungen() {
if (parallel) return tauschZaehlerParallel.get();
else return tauschZaehlerSeriell;
}
/**
* Anzahl der Vergleiche die zum Sortieren benoetigt wurden
* @return Anzahl der Vergleiche
*/
public long anzahlVergleiche() {
if (parallel) return vergleichszaehlerParallel.get();
else return vergleichszaehlerSeriell;
}
/**
* vergleicht zwei Zahlen a und b auf Größe
* @param a
* @param b
* @return wahr wenn a kleiner b ist
*/
public boolean istKleiner(int a, int b) {
vglZaehler();
if (geschwaetzig) {
System.out.println("Vergleich:feld["+a+"]<feld["+b+"] bzw. " +
feld[a] +"<"+ feld[b]);}
return (feld[a]<(feld[b]));
}
/**
* vergleicht zwei Zahlen a und b auf Größe
* @param a
* @param b
* @return wahr wenn a kleiner oder gleich b ist
*/
public boolean istKleinerGleich(int a, int b) {
vglZaehler();
if (geschwaetzig) {
System.out.println("Vergleich:feld["+a+"]<=feld["+b+"] bzw. " +
feld[a] +">"+ feld[b]);}
return (feld[a]<=(feld[b]));
}
/**
* diese Methode zaehlt alle Vergleiche. Sie ist mt-sicher
* für alle Algorithmen die das parallel Flag gesetzt haben
*/
public void vglZaehler() {
if (parallel) vergleichszaehlerParallel.getAndIncrement();
else vergleichszaehlerSeriell++;
}
/**
* Tausche den Inhalt der Position a mit dem Inhalt der Position b
* @param a
* @param b
*/
public void tausche(int a, int b) {
tZaehler();
if (geschwaetzig)
System.out.println("Getauscht:feld["+a+"<->"+b+"];f["+a
+ "]="+feld[b]+";feld["+b+"]="+feld[a]);
int s = feld[a];
feld[a] = feld[b];
feld[b] = s;
}
/**
* diese Methode zaehlt alle Vertauschungen. Sie ist mt-sicher
* für alle Algorithmen die das parallel Flag gesetzt haben
*/
public void tZaehler() {
if (parallel) tauschZaehlerParallel.getAndIncrement();
else tauschZaehlerSeriell++;
}
/**
* Belege das Feld mit Zufallswerten. Alte Belegungen werden gelöscht!
*/
public void generiereZufallsbelegung() {
// Generiere neue Belegung
maxWert = 2 * feld.length;
for (int i = 0; i < feld.length; i++) {
feld[i]=(int)(Math.random() * (double) maxWert);
}
}
/**
* Setzt Zaehler für Vertauschungen und Vergleiche zurueck auf Null
*/
public void zaehlerRuecksetzen() {
if (parallel) {
tauschZaehlerParallel.set(0);
vergleichszaehlerParallel.set(0);
}
else {
tauschZaehlerSeriell = 0;
vergleichszaehlerSeriell = 0;
}
}
}

 

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.

package s2.sort;
/**
*
* @author sschneid
* @version 2.0
*/
public class TrivialSort extends Sortierer{
/**
* Konstruktor: Akzeptiere ein Feld von int. Reiche
* das Feld an die Oberklasse weiter.
* Der Algorithmus ist nicht parallel (false Argument)
* @param s
*/
public TrivialSort(int[] s) { super(s,false); }
/**
* Diese Methode sortiert leider nur die beiden ersten Elemente
* auf der Position von und (von+1)
* @param von
* @param bis
*/
@Override
public void sortieren(int von, int bis) {
geschwaetzig = false;
int temp; // Zwischenspeicher
if (istKleiner(von+1,von)) {
tausche(von,von+1);
}
if (istKleiner(von+2,von+1)) {
tausche(von+1,von+2);
}
//druckenKonsole();
}
@Override
public String algorithmus() {
return "Sortiere drei Werte";
}
}