Allgemeines
Der sehr pragmatisch und passend benannter Sortieralgorithmus QuickSort ist eines der zeitlich effizientesten in seiner Kategorie. Deren Stärke bezieht er aus dem Konzept des Teilen und Herrschens.
Prozess
- Zu aller erst wird, ausgehend der zu sortierenden Liste, ein Element als sogenannter "pivot" (Trennpunkt) ausgewählt. Die Wahl des pivots ist massgebend bezüglich der Effizienz, garantiert wird sie jedoch nicht, da dies Wissen über die tatsächliche Reihenfolge voraussetzen würde. Deswegen entstanden über die Jahrzehnte zahlreiche Ansätze, den pivot klugerweise zu bestimmen. Im Code zuunterst wird der Lomuto Partitionierung Algorithmus angewandt, weil er am leichtesten zu implementieren ist.
- Zunächst werden alle Werte kleiner als der pivot auf deren linke Seite und die die grösser sind auf deren rechte Seite verschoben.
- Nun wird der 1. und 2. Schritt den linken und rechten Wertgruppierungen angewendet, bis ein einziges Element in der eingeschränkten Liste übrig bleibt.
Das untenstehende Grafik illustriert dieser Vorgang bildlich an einem Praxisbeispiel.
Quelle: https://www.techiedelight.com/wp-content/uploads/Quicksort.png
Als Code
Die folgende Codezeilen legen den Quicksort in Java dar:
class QuickSort
{
public static void main(String args[])
{
int array[] = {10, 7, 8, 9, 1, 5};
QuickSort sorter = new QuickSort();
sorter.sort(array, 0, array.length - 1);
for (int i = 0; i < array.length; ++i) {
System.out.print(array[i] + " ");
}
}
int partition(int array[], int scopeStart, int scopeEnd)
{
int pivot = array[scopeEnd];
int i = (scopeStart - 1);
for (int j = scopeStart; j < scopeEnd; j++)
{
if (array[j] <= pivot)
{
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = a[high];
array[high] = temp;
return i + 1;
}
void sort(int array[], int scopeStart, int scopeEnd)
{
if (scopeStart < scopeEnd)
{
int partitionIndex = partition(array, scopeStart, scopeEnd);
sort(array, scopeStart, partitionIndex - 1);
sort(array, partitionIndex + 1, scopeEnd);
}
}
}
Quelle: https://www.geeksforgeeks.org/java-program-for-quicksort/
DE 
EN 