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

Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden ist.

Implementierung: Klasse SelectionSort

package s2.sort;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class SelectionSort 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 SelectionSort(int[] s) {super(s,false);}
    /**
     * sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
     * zurück
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    @Override
    public void sortieren(int startIndex, int endeIndex){
        //geschwaetzig=true;
        int minimumIndex;
        for (int unteresEnde=startIndex; unteresEnde<endeIndex; unteresEnde++) {
            minimumIndex = unteresEnde; //Vergleichswert
            // Bestimme Position des kleinsten Element im Intervall
            for (int j=unteresEnde+1; j<=endeIndex; j++) {
                if (istKleiner(j,minimumIndex)) {
                    minimumIndex=j; // neuer Kandidat
                }
            }
            // Tausche kleinstes Element an den Anfang des Intervalls
            tausche(unteresEnde,minimumIndex);
            // das kleinste Element belegt jetzt das untere Ende des Intervalls
         }
    }
    /**
     * Liefert den Namen des SelectionSorts
     * @return
     */
    @Override
    public String algorithmus() {return "Sortieren durch Auswahl";}
}

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse InsertionSort

package s2.sort;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class InsertionSort 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 InsertionSort(int[] s) {
        super(s,false);
    }
    /**
     * sortiert ein Feld im Bereich startIndex bis endeIndex
     * @param startIndex
     * @param endeIndex
     */
    public void sortieren(int startIndex, int endeIndex) {
        for (int sortierGrenze = startIndex;sortierGrenze < endeIndex;
                sortierGrenze++) {
            int probe = sortierGrenze + 1;
            int j = startIndex;
            while (istKleiner(j, probe)) {
                j++;
            }
            // Verschiebe alles nach rechts.
            // Tausche den Probenwert gegen den unteren Nachbarn
            // bis man bei der Position j angekommen ist
            for (int k = probe - 1; k >= j; k--) {
                tausche(k, k + 1);
            }
        }
    }
    /**
     * Liefert den Namen des Insertion Sorts
     * @return
     */
    public String algorithmus() {
        return "Sortieren durch Einfuegen";
    }
}

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse BubbleSort

package s2.sort;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class BubbleSort 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 BubbleSort(int[] s) {super(s, false); }
    /**
     * sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
     * zurück
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    public void sortieren(int startIndex, int endeIndex) {
        boolean vertauscht;
        do {
            vertauscht = false;
            for (int i = startIndex; i+1 <= endeIndex; i++) {
                if (istKleiner(i + 1,i)) {
                    tausche(i,i+1);
                    vertauscht = true;
                }
            }
        } while (vertauscht);
    }
    /**
     * Liefert den Namen des Bubble Sorts
     * @return
     */
    public String algorithmus() {
        return "Bubble Sort";
    }
}

 Die folgende Implementierung implementiert die abstrakte Klasse Sortierer die in den Beispielprogrammen zum Sortieren zu finden sind.

Implementierung: Klasse Quicksort

package s2.sort;
/**
 *
 * @author sschneid
 */
public class QuickSort 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 QuickSort(int[] s) {
        super(s,false);
    }
    /**
     * sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
     * zurück
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    @Override
    public void sortieren(int startIndex, int endeIndex) {
        int i = startIndex;
        int j = endeIndex;
        int pivotWert = feld[startIndex+(endeIndex-startIndex)/2];
        //System.out.println("von"+ startIndex+", bis:"+endeIndex +
        //        " pivot:" + pivotWert);
        while (i<=j) {
           // Suche vom unteren Ende des Bereichs aufsteigend einen
           // Feldeintrag welcher groesser als das Pivotelement ist
           while (feld[i] < pivotWert) {i++;vglZaehler();}
           // Suche vom oberen Ende des Bereichs absteigend einen
           // Feldeintrag der kleiner als das Pivotelement ist
           while (feld[j] > pivotWert) {j--;vglZaehler();}
              // Vertausche beide Werte falls die Zeiger sich nicht
              // aufgrund mangelnden Erfolgs überschnitten haben
           if (i<=j) {
               tausche(i,j);
              i++;
              j--;
              }
         }
         // Sortiere unteren Bereich
         if (startIndex<j) {sortieren(startIndex,j);}
         // Sortiere oberen Bereich
         if (i<endeIndex)  {sortieren(i,endeIndex);}
    }
    /**
     * Liefert den Namen des Insertion Sorts
     * @return
     */
    @Override
    public String algorithmus() {
        return "QuickSort";
    }
}
 

Implementierung: Parallelisierter Quicksort

Die unten aufgeführte Klasse nutzt die "Concurrency Utilities" die in Java 7 eingeführt wurden. Aus der Sammlung wird das Fork/Join Framework verwendet.

Das Aufteilen des Sortierintervalls erfolgt hier seriell in einer eigenen Methode.

Das Sortieren der Teilintervalle erfolgt parallel solange das Intervall eine bestimmte Mindestgröße (100) besitzt.

Die Fork/Join Klassen stellen dem Algorithmus einen Pool von Threads zur Verfügung die sich nach der Anzahl des Prozessoren des Rechners richten.

Hierzu dient eine Spezialisierung der Klasse RecursiveAction. 

• Die Methode compute() wird in einem eigenen Thread durchgeführt wenn das dazugehörige Objekt mit der Methode invokeAll() aufgerufen wird. Diese Methode wird überschrieben.
• Die Methode invokeAll() erlaubt es neue Tasks zu in Auftrag zu geben. Diese Methode wird erst beendet wenn alle Tasks ausgeführt sind.

In der vorliegenden Implementierung erfolgt ein paralleler Aufruf eines Task zum Sortieren der Teilintervalle und nicht ein sequentieller Methodenaufruf.

Die Implementierung des Task erfolgt in der inneren Klasse Sorttask. Diese Klasse ummantelt quasi die Sortiermethode.

package s2.sort;
import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class QuickSortParallel extends Sortierer{
    static int SIZE_THRESHOLD=100; // Schwellwert für paralleles Sortieren
    private static final ForkJoinPool THREADPOOL = new ForkJoinPool();
    /**
     * Konstruktor: Akzeptiere ein Feld von int. Reiche
     * das Feld an die Oberklasse weiter.
     * Der Algorithmus ist  parallel (true Argument)
     * @param s
     */public QuickSortParallel(int[] s) {
        super(s, true);
    }
    /**
     * Innere statische Klasse die Fork and Join aus dem Concurrency package
     * implementiert. Sie macht aus Methodenaufrufen, Taskaufrufe von Threads
     */
    static class SortTask extends RecursiveAction {
        int lo, hi;
        QuickSortParallel qsp;
         /**
         * Speichere alle wichtigen Parameter für den Task
         * @param lo untere Intervallgrenze
         * @param hi obere Intervallgrenze
         * @param qsp Referenz auf das zu sortierende Objekt
         */
        SortTask(int lo, int hi, QuickSortParallel qsp) {
            this.lo = lo;
            this.hi = hi;
            this.qsp =qsp;
        }
        /**
         * Führe Task in eigenem Thread aus und nutze Instanzvariablen
         * als Parameter um Aufgabe auszuführen.
         */
        @Override
        protected void compute() {
            //System.out.println(" Thread ID => " + Thread.currentThread().getId());
            if (hi - lo < SIZE_THRESHOLD) {
                // Sortiere kleine Intervalle seriell
                qsp.sortierenSeriell(lo, hi);}
            else { // Sortiere große Intervalle parallel
                int obergrenzeLinkesIntervall;
                obergrenzeLinkesIntervall = qsp.teilsortieren(lo,hi);
                // der serielle rekursive Aufruf wird ersetzt durch
                // den parallelen Aufruf zweier Threads aus dem Threadpool
                //System.out.println("Parallel: "+
                //        lo+","+obergrenzeLinkesIntervall+","+hi);
                invokeAll(new SortTask(lo,obergrenzeLinkesIntervall,qsp),
                          new SortTask(obergrenzeLinkesIntervall+1,hi,qsp));
            }
        }
    }
    /**
     * sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
     * zurück
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    @Override
    public void sortieren(int startIndex, int endeIndex) {
        THREADPOOL.invoke(new SortTask(startIndex,endeIndex,this));
    }
    /**
     * sortiert ein Eingabefeld s und gibt eine Referenz auf dea Feld wieder
     * zurück
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    public void sortierenSeriell(int startIndex, int endeIndex) {
        if (endeIndex > startIndex) {
             int obergrenzeLinkesIntervall= teilsortieren(startIndex, endeIndex);
             //System.out.println("Seriell: "+
             //           startIndex+","+obergrenzeLinkesIntervall+","+endeIndex);
             // Sortiere unteren Bereich
             if (startIndex<obergrenzeLinkesIntervall) {
                sortierenSeriell(startIndex,obergrenzeLinkesIntervall);}
             // Sortiere oberen Bereich
             if (obergrenzeLinkesIntervall+1<endeIndex)  {
                sortierenSeriell(obergrenzeLinkesIntervall+1,endeIndex);}
        }
    }
    public int teilsortieren(int startIndex, int endeIndex) {
        int i = startIndex;
        int j = endeIndex;
        int pivotWert = feld[startIndex+(endeIndex-startIndex)/2];
        //druckenKonsole();
        while (i<=j) {
           // Suche vom unteren Ende des Bereichs aufsteigend einen
           // Feldeintrag welcher groesser als das Pivotelement ist
           while (feld[i] < pivotWert) {i++;vglZaehler();}
           // Suche vom oberen Ende des Bereichs absteigend einen
           // Feldeintrag der kleiner als das Pivotelement ist
           while (feld[j]> pivotWert) {j--;vglZaehler();}
              // Vertausche beide Werte falls die Zeiger sich nicht
              // aufgrund mangelnden Erfolgs überschnitten haben
           if (i<=j) {
              tausche(i,j);
              i++;
              j--;
              }
         }
        //System.out.println("von"+ startIndex+", bis:"+endeIndex +
        //        " pivot:" + pivotWert + " , return: " +i);
        return i-1;
    }
    /**
     * Liefert den Namen des Insertion Sorts
     * @return
     */
    public String algorithmus() {
        return "QuickSort mit Fork and Join";
    }
}
 

Hinweis: Dieser Algorithmus ist parallel. Er teilt dies der Oberklasse im Konstruktor als Parameter mit. Hierdurch werden die Zähler für die Vergleiche von Vertauschungen und Vergleichen vor einem parallelen Inkrement geschützt. Die Synchronisierung dieser Zählvariablen ist leider so aufwendig, dass der Algorithmus nicht mehr schneller als der seriell Algorithmus ist...

Man muss hier leider eine Entscheidung treffen:

• setzen des Flag auf true: Die Vertauschungen werden korrekt gezählt. Der Algorithmus ist korrekt und langsam.
• setzen des flag auf false: Die Veretauschungen und Vergleiche werden nicht korrekt gezählt. Der Algorithmus ist korrekt und schnell. Das bedeutet, er skaliert auf Mehrprozessorsystemen. 

Führen Sie einen Durchlauf des Quicksorts manuell durch. Teilen Sie ein gegebenes Sortierintervall (Aufgabe: Vorher) nach den Regeln des Quicksorts in zwei Unterintervalle die noch sortiert werden müssen.

• Sortieren Sie aufsteigend
• Wählen Sie das Pivotelement ganz rechts im Intervall.
  • Markieren Sie das Pivotelement in der Aufgabe mit einem Pfeil von unten (siehe Beispiel).
• Wenden Sie die Regeln des Quicksorts an. Zeichnen Sie zweiseitige Pfeile im "Vorher" Diagramm ein, um die notwendigen Vertauschungen zu markieren.
• Zeichnen Sie mit einem zweiseitigen Pfeil die nötige Vertauschung des Pivotelements im "Vorher" Diagramm ein.
• Tragen Sie alle neuen Werte im "Nachher" Diagramm ein.
• Zeichnen sie die beiden verbliebenen zu sortierenden Zahlenintevalle mit eckigen Linien (siehe "Vorher" Diagramm) ein.

Ein Feld f[1] bis f[N] mit Schlüsseln bildet einen Heap wenn die folgende Bedingung gilt:

Die Heapbedingung lässt sich leichter grafisch in einer Baumdarstellung verdeutlichen:

Das Feld f mit der Feldgröße N=9 f[1] = 9 f[2] = 8 f[3] = 7 f[4] = 3 f[5] = 6 etc. genügt der Heapbedingung da jeder obere Knoten größer als die beiden Unterknoten ist. Die Position im Feld wird hier in rot dargestellt. Der Schlüssel (Wert) des Feldelements hat einen gelben Hintergrund

Mit dem Bottom-Up Verfahren kann man die Heapbedingung für vollständig unsortierte Folgen von Schlüsseln herstellen.

Das Verfahren basiert auf der Idee, dass beginnend mit dem Schlüssel auf der höchsten Feldposition f[N] der Wert versickert wird um anschließend den nächst niedrigeren Wert F[N-1] zu versickern bis man den größten Wert f[1] versickert hat.

Beispiel

Grafische Visualisierung	Beschreibung
	Der gegebene Baum sei vollständig mit Zufallsschlüsseln belegt. Alle Werte sind zufällig. Die Positionen 5, 6,7,8 und 9 können nicht versickert werden, da sie keine Unterblattknoten zum Versickern haben.
	Das Bottom-Up Verfahren beginnt mit dem ersten Knoten i der über Unterknoten verfügt. Dieser Knoten ist immer die Position N/2 abgerundet. Bei N=9 ist die 9/2= 4.5. Der abgerundete Wert ist i=4. Hier muß f[8]=9 mit f[4]=3 getauscht werden um den Schlüssel zu versickern.
	Bei i=3 muss f[3]=4 mit f[7]=5 getauscht werden und ist damit auch versickert.
	Bei i=2 muss f[4] mit f[2] getauscht werden. Das rekursives Versickern bei f[4]=9 is nicht notwendig. f[4]=9 ist größer als f[8]=3 und f[9]=2
	Bei i=1 muss f[1] mit  f[2]=9 getauscht werden.
	Nach dem Neubesetzen der Position f[2]=7 zeigt sich aber, dass die Heapbedingung für den entsprechenden Teilbaum von f[2] nicht gilt da f[2|<f[2*i+1] ist. f[2] muss also rekursiv weiter versickert werden.
	Nach dem Tauschen von f[2]=7 mit f[5]=8 ist das rekursive Versickern beendet. f[5] hat keine Unterknoten da 5 > N/2 ist. Der Baum genügt jetzt der Heapbedingung

Herstellen der Heapbedingung

Top-Down-Verfahren

Dieses Verfahren dient der Herstellen der Heapbedingung, wenn schon für die Unterheaps für die Heapbedingung gilt.

Man wendet es an, nachdem man den größten Schlüssel entnommen hat und ihn durch den Wert mit dem größten Index im unsortierten Baum ersetzt hat.

Das Versickern dieses neuen Schlüssels an der Wurzel des Baums erfolgt mit den folgenden Schritten:

• Beginne mit der Position i=1 im Baum
• Der Schlüssel f[i] hat keine Unterknoten da 2*i>N ist,
  • Der Schlüssel kann nicht mehr versickert werden. Das Verfahren ist beendet. 
• Der Schlüssel f[i] hat noch genau einen Unterknoten f[i*2]
  • Der Schlüssel f[i] wird mit dem Schlüssel f[i*2] getauscht falls f[i]<f[i*2]. Das Verfahren ist nach diesem Schritt beendet.
• Der Schlüssel f[i] hat noch Unterknoten f[2*i] und f[2*i+1]
  • Der Schlüssel f[i] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
    • Das Verfahren ist beendet die Heapbedingung ist gegeben
  • Der Schlüssel f[i*2] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
    • Tausche die Schlüssel f[i] mit f[2*i]
    • Versickere den Schlüssel f[i*2] nach dem Top-Down Verfahren
  • Der Schlüssel f[i*2+1] ist der größte der drei Schlüssel f[i], f[i*2],f[i*2+1]
    • Tausche die Schlüssel f[i] mit f[2*i+1]
    • Versickere den Schlüssel f[i*2+1] nach dem Top-Down Verfahren

Diese rekursive Verfahren wird hier an einem Beispiel gezeigt:

Grafische Visualisierung	Beschreibung
	Durch das Entfernen des größten Schlüssels f[1] entstehen zwei Unterbäume für die die Heapbedingung nach wie vor gilt.
	Durch das Einsetzen eines Schlüssel von der Position N ist nicht mehr garantiert, dass die Heapbedingung für den gesamten Restbaum f[1] bis f[N-1]=f[8] gegeben ist. Der Schlüssel f[1]=2 ist eventuell größer als die Schlüssel f[2*1] und f[2*1+1]. In diesem Fall ist die Heapbedingung für f[1] bis f[8] schon gegeben. Es muss nichts mehr getan werden. Im vorliegenden Fall ist f[1]=2 aber nicht der größte Schlüssel. Er muss rekursiv versickert werden. Dies geschieht durch das Vertauschen mit f[2] = 8. f[3] = 7 ist nicht der richtige Kandidat. 7 ist nicht der größte der drei Schlüssel.
	Nach dem Vertauschen von f[1] mit f[2] gilt die Heapbedingung zwar für den obersten Knoten. Sie gilt jedoch nicht für den Teilbaum unter f[2]= 2. Der Schlüssel 2 muss weiter versickert werden. In diesem Fall ist f[5]=6 der größte Schlüssel mit dem f[2]= 2 vertauscht weden muss.
	Nach dem Vertauschen von f[2] mit f[5] gilt die Heapbedingung wieder für den gesamten Baum.

package s2.sort;
/**
 *
 * @author sschneid
 * @version 2.0
 */
public class HeapSort 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 HeapSort(int[] s) {super(s,false);}
    /**
     * sortiert ein Eingabefeld s
     * @param s ein unsortiertes Feld
     * @return ein sortiertes Feld
     */
    public void sortieren(int startIndex, int endeIndex){
        // Erzeugen der Heapbedingung, Bottom up...
        for (int i=(endeIndex-1)/2; i>=0; i--) versickere (i,endeIndex);
        //System.out.println("Heapbedingung hergestellt");
        for (int i=endeIndex; i>0; i--) {
            // Tausche das jeweils letzte Element mit dem Groeßten an der
            // Wurzel. Versickere die neue Wurzel und verkürze
            // das zu sortierende Intervall von hinten nach vorne
            tausche(0,i); // Groesstes Element von der Wurzel an das Ende
                // des Intervals getauscht
            versickere(0,i-1); // versickere die neue Wurzel um Heapbedingung
                // herzustellen
            }
        }
    /**
     * Berechne Index des linken Sohns für gegebenen Index
     * liefere -1 zurück falls keine linker Sohn existiert
     * @param index für den Sohn berechnet wird
     * @param endeIndex letzter belegter Indexplatz
     * @return
     */
    private int linkerSohn(int index, int endeIndex) {
        int ls = index*2+1;
        if (ls > endeIndex)
            return -1;
        else return ls;
    }
    /**
     * Berechne Index des linken Sohns für gegebenen Index
     * liefere -1 zurück falls keine linker Sohn existiert
     * @param index für den Sohn berechnet wird
     * @param endeIndex letzter belegter Indexplatz
     * @return
     */
    private int rechterSohn(int index, int endeIndex) {
        int rs = (index+1)*2;
        if (rs > endeIndex)
            return -1;
        else return rs;
    }
    /**
     * Versickere ein Element auf der Position "vers"
     * @param vers Index des zu versickernden Elements
     * @param endeIndex hoechste Indexposition die zum Verisckern zur Verfügung
     *                  steht. Sie wird bei der Berechnung des rechts Sohns
     *                  benötigt
     */
    private void versickere (int vers, int endeIndex) {
        int ls = linkerSohn(vers,endeIndex);
        int rs = rechterSohn(vers,endeIndex);
        int groessererSohn;
        while (ls != -1) { // Es gibt einen linken Sohn
            // Versickere bis Heapbedingung erfüllt ist oder keine
            // Söhne mehr vorhanden sind
            groessererSohn =ls; // linker Sohn als groesseren Sohn nominieren
            if ((rs != -1) && (istKleiner(ls,rs))) groessererSohn = rs;
                    // der rechte Sohn existiert und war groesser...
            if (istKleiner(vers,groessererSohn)) {
                tausche(vers,groessererSohn); // beide Felder wurden getauscht
                vers = groessererSohn;
                ls = linkerSohn(vers,endeIndex);
                rs = rechterSohn(vers,endeIndex);
            }
            else ls=-1; // Abbruchbedingung für while Schleife
        }
    }
    /**
     * Liefert den Namen des Heap Sorts
     * @return
     */
    public String algorithmus() {return "Heap Sort";}
}