Der Quicksort ist effizienter als der Bubblesort, vor allem für große Arrays aber auch etwas komplexer.
Auch hier verwenden wir den Quicksort um ganze Zahlen des Typ Integer zu sortieren. Der Quicksort wählt ein Element als Pivot (Erklärung unten) und teilt das Array in 2 Teile.
So sind dann alle Elemente kleiner des Pivot auf der linken Seite und die größer als das Pivot sind auf der rechten Seite.
public void QuickSort(int[] arr, int start, int end)
{
if (start < end)
{
int pivotIndex = Partition(arr, start, end);
QuickSort(arr, start, pivotIndex - 1);
QuickSort(arr, pivotIndex + 1, end);
}
}
private int Partition(int[] arr, int start, int end)
{
int pivot = arr[end];
int i = start - 1;
for (int j = start; j <= end - 1; j++)
{
if (arr[j] < pivot)
{
i++;
Swap(arr, i, j);
}
}
Swap(arr, i + 1, end);
return i + 1;
}
private void Swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
#endregion
}Erklärung Pivot
Beim Quicksort-Algorithmus ist der Pivot ein zentrales Element, welches verwendet wird um die zu sortierende Liste in 2 Listen aufzuteilen.
Zuerst wird ein Element aus der zu ordnenden Liste ausgewählt, z.B. das erste Element, das letzte Element oder auch ein zufälliges Element.
Ist das Pivot ausgewählt, werden alle Elemente welche kleiner oder gleich sind nach links verschoben und alle die größer sind nach rechts verschoben. Nachdem die zu sortierende Liste in 2 Listen aufgeteilt ist (Linke und Rechte) wird rekursiv der Quicksort-Algorithmus auf beiden Teillisten angewendet bis alle Teillisten nur noch ein Element enthält, oder leer ist.