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;

import java.lang.reflect.Constructor;
import java.lang.reflect.InvocationTargetException;
import java.util.Arrays;

/**
 *
 * @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;
        return sort;
    }

/**
* 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");
      break; 
   }
   sort.zaehlerRuecksetzen();
}
}
}

 Die Quellen bei github.

 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;
        }
    }
}

 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";
    }
}