Der Algorithmus
Der QuickSort-Algorithmus ist ein vorwiegend rekursiver Sortieralgorithmus nach dem Teile- und Herrsche-Prinzip. Er lässt sich aber auch iterativ implementieren. Er ruft sich so lange selber auf, bis sich zwei Pointer auf Array-Elemente von links und rechts treffen oder eine Teilliste in einem Rekursionsschritt nur noch aus einem Element besteht. Alle Array-Elemente auf der linken und rechten Stack-Seite eines festgelegtem oder zufällig gewähltem Pivot-Elements sind nach jedem Rekursionsschritt jeweils kleiner (linke Seite) oder größer (rechte Seite). Dabei wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt.
Oder anders: Quicksort wählt ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.
Anschließend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekusion.
Der Prinzip:
- Auswahl eines festem oder zufälligem Pivot-Elements (muss nicht das kleinste Element im Array sein)
- Sortierung aller kleineren Zahlen als das Pivot-Element auf die linke Seite des Stapels/Stacks
- Sortierung aller größeren Zahlen als das Pivot-Element auf die rechte Seite des Stapels/Stacks
- Rekursiver Aufruf für die linke Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine kleinere Zahl mehr gefunden wurde, die links vom Pivot-Element einsortiert werden kann.
- Rekursiver Aufruf für die rechte Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine größere Zahl mehr gefunden wurde, die rechts vom Pivot-Element einsortiert werden kann.
package AlgoDat;
public class QuickSort {
// Zu sortierendes Array
private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
// Hält die Klasse als instanziertes Objekt
@SuppressWarnings("unused")
private static QuickSort program;
private java.util.Random rnd = new java.util.Random();
// Hilfsfunktion für das Ausgeben des Arrays
public void OutputOfIntArray(int myArray[])
{
if (myArray != null)
{
for (int i = 0; i < myArray.length; i++) {
if (i > 0) System.out.print(";");
System.out.print(myArray[i]);
}
System.out.println();
}
}
// Generiert ein zufälliges Integer-Array der Größe size mit Werten zwischen 0 und upperLimit
public int[] generateIntegerArrayOfSize(int size, int upperLimit)
{
int[] generatedArray = new int[size];
for (int i = 0; i < generatedArray.length; i++)
{
generatedArray[i] = rnd.nextInt(upperLimit);
}
return generatedArray;
}
public void makeQuickSort(int[] arrayToSort, int fromIndex, int toIndex)
{
// Rekursionsabbruch
if (fromIndex >= toIndex)
{
return;
}
// Das Pivot-Element muss beim Teile-Herrsche-Prinzip nicht die kleinste Zahl im Array sein
// und kann willkürlich gewählt werden - wie hier das letzte Element des Array
// int pivot = arrayToSort[toIndex];
// Im Average Case performt der Quicksort aber besser, wenn es zufällig ausgewählt wird
// Zufälliges Pivot-Element?
boolean zufallsPivotElement = true;
int pivotIndex = zufallsPivotElement ? pivotIndex = rnd.nextInt(toIndex - fromIndex) + fromIndex : toIndex;
int pivot = arrayToSort[pivotIndex];
System.out.println("Ich will das Pivot am Index: " + pivotIndex + "("+ pivot +")");
// Vertausche das Pivot-Element damit es am Schluss der Liste steht
this.vertausche(arrayToSort, pivotIndex, toIndex);
// Diese Pointer beinhalten den Index der Elemente, die miteinander verglichen und
// ggfs. vertauscht werden, wenn sie kleiner/größer als das Pivot sind.
int leftPointer = fromIndex;
int rightPointer = toIndex - 1;
// Partitioniere, so lange wie sich die Pointer nicht in die Quere kommen
while (leftPointer < rightPointer)
{
// Verschiebe leftPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
// (oder wie sich die Pointer nicht überschneiden)
while (arrayToSort[leftPointer] <= pivot && leftPointer < rightPointer)
{
leftPointer++;
}
// Verschiebe rightPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
// (oder wie sich die Pointer nicht überschneiden)
while (arrayToSort[rightPointer] >= pivot && leftPointer < rightPointer)
{
rightPointer--;
}
// Vertausche die Elemente am Index von leftPointer und rightPointer
this.vertausche(arrayToSort, leftPointer, rightPointer);
}
// Vertausche die Elemente am Array-Index von leftPointer und toIndex
if(arrayToSort[leftPointer] > arrayToSort[toIndex])
{
this.vertausche(arrayToSort, leftPointer, toIndex);
}
else
{
leftPointer = toIndex;
}
// QuickSort für die linke Seite vom Pivot-Element
this.makeQuickSort(arrayToSort, fromIndex, leftPointer - 1);
// QuickSort für die rechte Seite vom Pivot-Element
this.makeQuickSort(arrayToSort, leftPointer + 1, toIndex);
}
public void vertausche(int[] arrayToSwap, int idx1, int idx2)
{
int swapVar = arrayToSwap[idx1];
arrayToSwap[idx1] = arrayToSwap[idx2];
arrayToSwap[idx2] = swapVar;
}
// Konstruktor
public QuickSort()
{
System.out.print("Vorher: ");
this.OutputOfIntArray(myArray);
long startZeit = System.nanoTime();
// this.OutputOfIntArray(this.generateIntegerArrayOfSize(1000, 100));
this.makeQuickSort(myArray, 0, myArray.length - 1);
long endZeit = System.nanoTime();
System.out.print("Nachher: ");
this.OutputOfIntArray(myArray);
System.out.println("Ich habe " + (endZeit - startZeit) + " ns gebraucht.");
}
public static void main(String[] args)
{
// Instanziere aus den statischem Programm ein echtes Objekt
// damit nicht alle Methoden und Variablen static sein müssen.
program = new QuickSort();
}
}
Ausgabe
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Ich will das Pivot am Index: 0(22)
Ich will das Pivot am Index: 4(10)
Ich will das Pivot am Index: 1(6)
Ich will das Pivot am Index: 0(1)
Ich will das Pivot am Index: 2(2)
Ich will das Pivot am Index: 3(4)
Ich will das Pivot am Index: 7(7)
Ich will das Pivot am Index: 7(8)
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Ich habe 29708200 ns gebraucht.
Komplexität: O-Notation (Ordnung)
Der Quick-Sort hat im Best- und im Average-Case die Komplexität O(n* log(n)) und im Worst-Case die Komplexität O(n²)
