Quicksort: Implementierung in Java

 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.