Wie wird die Effizienz des Quicksort-Algorithmus je nach Situation bewertet?

Die Effizienz des Quicksort-Algorithmus hängt von der Wahl des Pivotelements und der Datenstruktur ab:

• Durchschnittliche Zeit: O(n log n) — bei zufälliger oder gut gewählter Pivotelementwahl.
• Schlechteste Zeit: O(n²) — wenn das Pivotelement immer ungünstig gewählt wird (z.B. das größte oder kleinste Element in einem bereits sortierten Array).

In der Praxis wird zur Effizienzsteigerung oft eine zufällige Wahl des Pivotelements oder die Medianwahl aus mehreren Elementen verwendet.

QuickSort ist in der Regel schneller als andere Sortieralgorithmen aufgrund seiner guten Lokalität und niedrigen Overheads, aber für sehr kleine Arrays oder fast sortierte Daten sind Einfüge- oder Mergesort manchmal vorzuziehen.

Beispiel für die Wahl des Pivotelements:

int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // einfache Wahl des letzten Elements
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            std::swap(arr[i], arr[j]);
        }
    }
    std::swap(arr[i + 1], arr[high]);
    return i + 1;
}

Zur Verbesserung kann ein zufälliges Pivot oder die Medianwahl aus drei Elementen verwendet werden.