Quicksort: Sortieren durch rekursives Teilen

Der Quicksort ist ein Verfahren welches auf dem Grundprinzip des rekursiven Teilens basiert:

  • Man nimmt ein beliebiges Pivotelement als Referenz (Pivotpunkt: Drehpunkt, Angelpunkt)
  • Man teilt die unsortierte Folge in drei Unterfolgen
    • Alle Elemente die kleiner oder gleich dem Pivotelement sind
    • Das Pivotelement
    • Alle Element die größer oder gleich dem Pivotelement sind

Die Unterfolgen die größer bzw. kleiner als das Pivotelement sind, sind selbst noch unsortiert. Das Pivotelement steht bereits an der richtigen Position zwischen den zwei Teilfolgen.

Durch rekursives Sortieren werden auch sie sortiert.

Der Quicksort wurde 1962 von C.A.R. Hoare (Computer Journal) veröffentlicht.

Verfahren

  • Folgen die aus keinem oder einem Element bestehen bleiben unverändert.
  • Wähle ein Pivotelement p der Folge F und teile die Folge in Teilfolgen F1 und F2 derart das gilt:
    • F1 enhält nur Elemente von F ohne das Pivotelement p die kleiner oder gleich p sind
    • F2 enhält nur Elemente von F ohne das Pivotelement p die größer oder gleich p sind
  • Die Folgen F1 und F2 werden rekursiv nach dem gleichen Prinzip sortiert
  • Die Ergebnis der Sortierung ist eine Aneinanderreihung der der Teilfolgen F1, p, F2.

Anmerkung: Der Quicksort folgt dem allgemeinen Prinzip von "Teile und herrsche" (lat.: "Divide et impera", engl. "Divide and conquer")

Beispiel

Im ersten Schritt wird das vollständige Feld vom Index 1 bis 7 sortiert, indem der Wert 23 auf dem Index 7 als  Pivotwert (Vergleichswert) gewählt.

Es wird nun vom linken Ende des Intervals (Index 1) aufsteigend das erste Element gesucht welches größer als das Pivotelement ist. Hier ist es der Wert 39 auf dem Index 2. Anschließend wird vom oberen Ende des Intervals von der Position links vom Pivotelement absteigend das erste Element gesucht welches kleiner als das Pivotelement ist. Hier ist es der Wert 19 auf dem Index 6.

Im nächsten Schritt werden die beiden gefundenen Werte getauscht und liegen nun in der "richtigen" Teilfolge.

Jetzt wird die Suche von links nach rechts weitergeführt bis das nächste Element gefunden ist welches größer als das Pivotelement ist. Hier ist es 35 auf Position 3. Die fallende Suche von Rechts endet bei dem Wert 17 auf Index 5. Die beiden Werte werden dann getauscht.

Nach der Vertauschung wird die aufsteigende Suche von Links weitergeführt und endet beim Wert 28 auf dem Index 4. Die fallende Suche von Rechts endet sofort da der Suchindex der steigenden Suche erreicht ist.

Der Pivotwert 23 auf Index 7 wird jetzt mit 28 auf dem Index  getauscht und hat seine korrekte Endposition erreicht.

Der Sortiervorgang wird jetzt rekursiv im Intervall 1 bis 3 und 5 bis 7 fortgeführt. Wie zuvor werden die Werte auf dem höchsten Index der Unterintervalle wieder als Pivotwerte gewählt.

Im linken Unterintervall endet die aufsteigende Suche schnell beim Wert 19 auf Index 2 der dann mit dem Pivotwert 17 getauscht wird. Im rechten Unterintervall muss bei der aufsteigenden suche der Wert 35 auf Index 5 mit dem Pivotwert 28 getauscht werden.

Bei den weiteren Teilungen in Unterintervalle bleiben nur noch das Intervall von Index 1 bis 2 sowie das Intervall von Index 6 bis 7 übrig. Hier werden wieder die Elemente am rechten Rand als Pivotwerte gewählt.

Im linken Unterintervall durchläuft die aufsteigende Suche das einzige Element und endet ohne Vertauschung. Im rechten Intervall muss ein letztes mal der Wert 39 mit 35 getauscht werden.

Aufwand

Der Quicksort ist in normalen Situationen mit einem Aufwand von n*log(n) sehr gut für große Datenmengen geeignet. Er ist einer der schnellsten Algorithmen. Bei sehr ungünstigen Sortierfolgen (schon sortiert) kann er aber auch mit einem quadratischen Aufwand sehr ineffizient sein.

Vorsortierte Folgen sind durchaus häufig bei realen Problemen zu finden. Der Quicksort ist bei schon sortierten Folgen sehr ineffizient ist und daher ist der Einsatz bei realen Anwendungen durchaus heikel.

 

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. 

 

Übung (Quicksort)

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.

Lösung (Quicksort)