Der heutzutage wohl am häufigsten eingesetzte Sortieralgorithmus nennt sich QuickSort. Es existieren einige Varianten dieses Algorithmus, dessen grundlegende Version, die in diesem Abschnitt vorgestellt wird, bereits 1960 von C. A. R. Hoare entwickelt wurde. Der Erfolg von QuickSort beruht darauf, dass er zum einen leicht verständlich und zum anderen im Mittel schneller ist, als jeder andere Sortieralgorithmus.
QuickSort zerlegt (man spricht auch von Partitionierung) das zu sortierende Array in zwei Teil-Arrays, die durch ein Referenz-Element - auch Pivot-Element genannt - getrennt werden. Alle Elemente des einen Teil-Arrays sind dabei kleiner oder gleich alle Elemente des anderen Teil-Arrays größer oder gleich dem Wert des Pivot-Elementes. Das bedeutet gleichzeitig, dass das Pivot-Element an seinem korrekten Platz im Array steht. Anschließend wird QuickSort rekursiv für die beiden Teil-Arrays aufgerufen. Die Rekursion endet, wenn das Teil-Array nur noch aus einem Element besteht.
Etwas ausführlicher lässt sich das zugrunde liegende Prinzip des Algorithmus folgendermassen skizzieren:
Eine einfache Strategie zur Implementierung der Partitionierung (Punkte 1 bis 5) ist folgende: Als Pivot-Element wird willkürlich das rechte Element des (Teil-)Arrays gewählt. Von links wird das Array nach einem Element durchsucht, das größer als das Pivot-Element ist. Von rechts wird das Array nach einem Element durchsucht, das kleiner als das Pivot-Element ist. Diese beiden Elemente sind offensichtlich jeweils im falschen Teil-Array und werden daher getauscht. Mit dieser Suche und dem Austausch wird fortgefahren, bis sich die Suchzeiger treffen bzw. kreuzen. Dann ist sicher gestellt, dass alle Elemente links vom linken Zeiger kleiner oder gleich und alle Elemente rechts vom rechten Zeiger größer oder gleich dem Pivot-Element sind. Als Index des Pivot-Elementes wählt man abschließend den Index, auf den der linke Zeiger zeigt, und tauscht dieses Element (das ja größer oder gleich dem Pivot-Element ist) mit dem Pivot-Element ganz rechts im Array.
Die Wahl des Pivot-Elementes ist eine viel diskutierte Eigenschaft des QuickSort-Algorithmus, da davon maßgeblich die Geschwindigkeit des Algorithmus beeinflusst wird. Wir haben das Element am rechten Rand gewählt. Unglücklich ist, wenn das gewählte Element das größte oder kleinste Element des Arrays ist, weil dies eine sehr ungleichmäßige Zerlegung des Arrays in Teil-Arrays und einen häufigen rekursiven Aufruf des Algorithmus bedingt.
In der Literatur wird oft das mittlere Element genommen. Prinzipiell ist die Wahl jedoch beliebig. Man kann auch bspw. drei Elemente auswählen und davon das Element mit dem mittleren Wert nehmen. Der oben beschriebene Partitionierungsalgorithmus muss in diesen Fällen einfach dahingehend abgeändert werden, dass nach der Wahl des Pivot-Elementes dieses zunächst mit dem Element ganz rechts im (Teil-)Array getauscht wird.
Die folgende Klasse QuickSort (QuickSort.ham) implementiert das Interface SortierAlgorithmus entsprechend des QuickSort-Algorithmus:
public class QuickSort implements SortierAlgorithmus {
// sortiert das uebergebene Array in aufsteigender Reihenfolge
// gemaess dem QuickSort-Algorithmus
public void sortiere(int[] zahlen) {
quickSort(zahlen, 0, zahlen.length-1);
}
// der Quicksort-Algorithmus wird auf dem Array zwischen den
// angegebenen Indizes ausgefuehrt
private void quickSort(int[] zahlen, int linkerIndex, int rechterIndex) {
if (linkerIndex < rechterIndex) {
int pivotIndex = zerlege(zahlen, linkerIndex, rechterIndex);
quickSort(zahlen, linkerIndex, pivotIndex-1);
quickSort(zahlen, pivotIndex+1, rechterIndex);
}
}
// liefert den Index des Pivot-Elementes und ordnet das Array innerhalb
// der angegebenen Indizes so um, dass alle Zahlen links vom Index
// kleiner oder gleich und alle Zahlen rechts vom Index groesser
// oder gleich dem Pivot-Element sind
private int zerlege(int[] zahlen, int linkerIndex, int rechterIndex) {
int pivotIndex = waehlePivotIndex(zahlen, linkerIndex, rechterIndex);
int pivotWert = zahlen[pivotIndex];
// das Pivot-Element kommt nach ganz rechts im Array
tauschen(zahlen, pivotIndex, rechterIndex);
int l = linkerIndex-1;
int r = rechterIndex;
// ordne das Array so um, dass jeweils alle Elemente links vom
// Zeiger l kleiner und alle Elemente rechts vom Zeiger r groesser
// als das Pivot-Element sind
do {
l++;
while (l <= rechterIndex && zahlen[l] <= pivotWert) l++;
r--;
while (r >= linkerIndex && zahlen[r] >= pivotWert) r--;
if (l < r) {
tauschen(zahlen, l, r);
}
} while (l < r);
// platziere das Pivot-Element an seine korrekte Position
if (l < rechterIndex) {
tauschen(zahlen, l, rechterIndex);
return l;
} else {
return rechterIndex;
}
}
// waehlt einen beliebigen Index zwischen den angegebenen Indizes
private int waehlePivotIndex(int[] zahlen, int linkerIndex, int rechterIndex) {
// in diesem Fall einfach der mittleren Index
return (linkerIndex + rechterIndex) / 2;
/* Alternative 1:
return rechterIndex;
*/
/* Alternative 2 (mittleres von drei Elementen):
int index1 = (linkerIndex + rechterIndex) / 2;
int index2 = (linkerIndex + index1) / 2;
int index3 = (index1 + rechterIndex) / 2;
if (zahlen[index1] <= zahlen[index2] &&
zahlen[index2] <= zahlen[index3])
return zahlen[index2];
if (zahlen[index2] <= zahlen[index3] &&
zahlen[index3] <= zahlen[index1])
return zahlen[index3];
return zahlen[index1];
*/
}
// tauscht die Elemente des Arrays an den angegebenen Indizes
private void tauschen(int[] zahlen, int index1, int index2) {
if (index1 != index2) {
int help = zahlen[index1];
zahlen[index1] = zahlen[index2];
zahlen[index2] = help;
}
}
}
Die folgende Hamster-Klasse QuickSortHamster (QuickSortHamster.ham) implementiert das Interface SortierHamster und visualisiert dabei den QuickSort-Algorithmus. Voraussetzung ist, dass es im Territorium zwei nicht durch Mauern blockierte Reihen unterhalb des Standard-Hamsters gibt. In der ersten Reihe unterhalb der Körnerhaufenreihe markieren zwei Markierungshamster jeweils den linken und rechten Rand des aktuell betrachteten Teil-Arrays. Der rechte Hamster zeigt also auch auf das Pivot-Element. Zwei weitere Markierungshamster in der Reihe darunter entsprechen den Suchzeigern des Partitionierungsalgorithmus.
// Demonstration des QuickSort-Algorithmus
public class QuickSortHamster
extends KoernerHaufenSortierHamster
implements SortierHamster
{
private MarkierungsHamster linkerIndexHamster = null;
// markiert den linken Rand des aktuellen Teil-Arrays
private MarkierungsHamster rechterIndexHamster = null;
// markiert den rechten Rand des aktuellen Teil-Arrays
// (gleichzeitig auch das Pivot-Element!)
private MarkierungsHamster linkerZeigerHamster = null;
// markiert waehrend der Partitionierung das aktuell
// betrachtete linke Element
private MarkierungsHamster rechterZeigerHamster = null;
// markiert waehrend der Partitionierung das aktuell
// betrachtete rechte Element
private int anzahlKoernerHaufen = 0;
// Anzahl der zu sortierenden Koernerhaufen
// Konstruktor
public QuickSortHamster(boolean mitErlaeuterungen) {
super(mitErlaeuterungen);
this.erlaeuterung(
"Ich sortiere die Koernerhaufen auf der Basis des QuickSort-Algorithmus.");
this.linkerIndexHamster =
new MarkierungsHamster(this.getReihe()+1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.linkerIndexHamster.erlaeuterung(
"Ich markiere den linken Rand des aktuell betrachteten Teil-Arrays.");
this.rechterIndexHamster =
new MarkierungsHamster(this.getReihe()+1, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.rechterIndexHamster.erlaeuterung(
"Ich markiere den rechten Rand des aktuell betrachteten Teil-Arrays " +
" und\ngleichzeitig auch den aktuellen Pivot-Haufen.");
this.linkerZeigerHamster =
new MarkierungsHamster(this.getReihe()+2, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.linkerZeigerHamster.erlaeuterung(
"Ich markiere waehrend der Partitionierung den aktuell " +
"betrachteten linken Haufen.");
this.rechterZeigerHamster =
new MarkierungsHamster(this.getReihe()+2, this.getSpalte(),
this.getReihe(), mitErlaeuterungen);
this.rechterZeigerHamster.erlaeuterung(
"Ich markiere waehrend der Partitionierung den aktuell " +
"betrachteten rechten Haufen.");
}
// Der Standard-Hamster steht mit Blickrichtung OST irgendwo im Territorium.
// Ein Vertretungshamster soll die Koernerhaufen bis zur nächsten Wand in
// aufsteigender Reihenfolge sortieren.
// Voraussetzung: Unterhalb des Standard-Hamsters existieren zwei nicht
// durch Mauern blockierte Reihen.
public void sortiereKoernerHaufen() {
this.erlaeuterung(
"Ich zaehle nun die Anzahl der zu sortierenden Koernerhaufen.");
this.anzahlKoernerHaufen = this.ermittleAnzahlKoernerHaufen();
this.erlaeuterung(
"Die Anzahl der zu sortierenden Koernerhaufen betraegt " +
this.anzahlKoernerHaufen +
",\nd.h. die Indizes der Haufen liegen zwischen 0 und " +
(this.anzahlKoernerHaufen-1) +
".");
this.quickSort(0, this.anzahlKoernerHaufen-1);
this.beendeSortierung();
}
// der Quicksort-Algorithmus wird auf dem Array zwischen den
// angegebenen Indizes ausgefuehrt
private void quickSort(int linkerIndex, int rechterIndex) {
if (linkerIndex < rechterIndex) {
this.linkerIndexHamster.markiereIndex(linkerIndex);
this.rechterIndexHamster.markiereIndex(rechterIndex);
this.erlaeuterung(
"Ich partitioniere nun das Teil-Array zwischen den Indizes " +
linkerIndex +
" und " +
rechterIndex +
".");
int pivotIndex = zerlege(linkerIndex, rechterIndex);
this.erlaeuterung(
"Die Partitionierung des Teil-Arrays zwischen den Indizes " +
linkerIndex +
" und " +
rechterIndex +
" ist abgeschlossen.\n" +
"Der Pivot-Haufen befindet sich bei Index " +
pivotIndex +
".");
quickSort(linkerIndex, pivotIndex-1);
quickSort(pivotIndex+1, rechterIndex);
}
}
// liefert den Index des Pivot-Elementes und ordnet das Array innerhalb
// der angegebenen Indizes so um, dass alle Zahlen links vom Index
// kleiner oder gleich und alle Zahlen rechts vom Index groesser
// oder gleich dem Pivot-Element sind
private int zerlege(int linkerIndex, int rechterIndex) {
int pivotIndex = waehlePivotIndex(linkerIndex, rechterIndex);
this.laufeZuIndex(pivotIndex);
int pivotWert = this.liefereAnzahlKoerner();
this.erlaeuterung(
"Ich stehe nun auf dem Pivot-Haufen. Hier liegen " +
pivotWert +
" Koerner.");
// das Pivot-Element kommt nach ganz rechts ins Array
this.erlaeuterung(
"Ich tausche nun den Pivot-Haufen mit dem rechten " +
"Haufen des\naktuellen Teil-Arrays (gelber Markierungshamster).");
this.tauschen(pivotIndex, rechterIndex);
int l = linkerIndex-1;
this.linkerZeigerHamster.markiereIndex(l);
int r = rechterIndex;
this.rechterZeigerHamster.markiereIndex(r);
// ordne das Array so um, dass jeweils alle Elemente links vom Zeiger l
// kleiner gleich und alle Elemente rechts vom Zeiger r groesser
// gleich dem Pivot-Element sind
this.erlaeuterung(
"Das Teil-Array zwischen den Indizes " +
linkerIndex +
" und " +
rechterIndex +
" wird nun so umgeordnet,\ndass jeweils alle Haufen links vom " +
"hellblauen Markierungshamster kleiner gleich\n" +
"und alle Elemente rechts vom violetten Markierungshamster " +
"groesser gleich\ndem Pivot-Haufen (gelber Markierungshamster) sind.");
do {
l++;
this.linkerZeigerHamster.markiereIndex(l);
while (l <= rechterIndex &&
this.linkerZeigerHamster.liefereAnzahlKoerner() <= pivotWert) {
l++;
this.linkerZeigerHamster.markiereIndex(l);
}
r--;
this.rechterZeigerHamster.markiereIndex(r);
while (r >= linkerIndex &&
this.rechterZeigerHamster.liefereAnzahlKoerner() >= pivotWert) {
r--;
this.rechterZeigerHamster.markiereIndex(r);
}
if (l < r) {
this.erlaeuterung(
"Der Haufen bei Index " +
l +
" ist groesser als der Pivot-Haufen\nund der Haufen bei Index " +
r +
" ist kleiner als der Pivot-Haufen.\nSie werden daher getauscht.");
tauschen(l, r);
}
} while (l < r);
// platziere das Pivot-Element an seine korrekte Position
if (l < rechterIndex) {
this.erlaeuterung(
"Die Umordnung des Teil-Arrays ist abgeschlossen.\n" +
"Nun muss ich nur noch den Pivot-Haufen (gelber Markierungshamster) " +
"an seine\nkorrekte Position bei Index " +
l +
" (hellblauer Markierungshamster) stellen.");
tauschen(l, rechterIndex);
return l;
} else {
this.erlaeuterung(
"Die Umordnung des Teil-Arrays ist abgeschlossen.\n" +
"Auch der Pivot-Haufen steht bereits an seiner korrekten " +
"Position bei Index " +
rechterIndex +
".");
return rechterIndex;
}
}
// waehlt einen beliebigen Index zwischen den angegebenen Indizes
private int waehlePivotIndex(int linkerIndex, int rechterIndex) {
// in diesem Fall einfach der mittleren Index
return (linkerIndex + rechterIndex) / 2;
/* Alternative 1:
return rechterIndex;
*/
/* Alternative 2 (mittleres von drei Elementen):
int index1 = (linkerIndex + rechterIndex) / 2;
int index2 = (linkerIndex + index1) / 2;
int index3 = (index1 + rechterIndex) / 2;
if (zahlen[index1] <= zahlen[index2] &&
zahlen[index2] <= zahlen[index3])
return zahlen[index2];
if (zahlen[index2] <= zahlen[index3] &&
zahlen[index3] <= zahlen[index1])
return zahlen[index3];
return zahlen[index1];
*/
}
// tauscht die Elemente des Arrays an den angegebenen Indizes
private void tauschen(int index1, int index2) {
if (index1 != index2) {
this.laufeZuIndex(index1);
int koerner1 = this.nimmAlle();
this.laufeZuIndex(index2);
int koerner2 = nimmAlle();
this.gib(koerner1);
this.laufeZuIndex(index1);
this.gib(koerner2);
}
}
private void beendeSortierung() {
this.laufeZuSpalte(this.startSpalte);
this.setzeBlickrichtung(Hamster.OST);
this.erlaeuterung("Sortierung erfolgreich beendet!");
}
}
Mit dem folgendem objektorientierten Hamster-Programm (SortierenMitQuickSort) (SortierenMitQuickSort.ham) können Sie sich von den Hamstern den QuickSort-Algorithmus demonstrieren lassen.
void main() {
Hamster paul = Hamster.getStandardHamster();
String antwort =
Hamster.getStandardHamster().liesZeichenkette(
"Moechten Sie textuelle Erlaeuterungen (ja/nein)?");
SortierHamster sortierer = new QuickSortHamster(antwort.equals("ja"));
sortierer.sortiereKoernerHaufen();
}
Der QuickSort-Algorithmus ist nicht stabil. QuickSort arbeitet in-place.
Die Geschwindigkeit von QuickSort ist abhängig von der Gleichmäßigkeit der
Partitionierung. Wenn die Wahl des Pivot-Elementes bewirkt, dass die beiden Teil-Arrays in jedem Rekursionsschritt
in etwa gleich groß sind, benötigt QuickSort 
Vergleiche.
Im ungünstigsten Fall sind jedoch 
Vergleiche notwendig, nämlich genau dann
wenn ein Teil-Array stets nur aus einem Element und das andere aus den restlichen Elementen besteht.
n ist dabei die Anzahl an zu sortierenden Elementen.
Im Web finden sich zahlreiche weitere Informationen zum QuickSort-Algorithmus, z.B. unter