Jaka jest złożoność czasowa algorytmu szybkiego sortowania w najgorszym przypadku?

Złożoność czasowa algorytmu szybkiego sortowania (QuickSort) w najgorszym przypadku wynosi O(n²), gdzie n to liczba elementów do posortowania.

Najgorszy scenariusz występuje, gdy element pivot (pivot) jest wybierany w taki sposób, że podział tablicy jest jak najbardziej nierówny — na przykład, gdy pivot zawsze jest najmniejszym lub największym elementem, a jedna z części zawiera n-1 elementów, a druga 0.

W tym przypadku rekurencja zamienia się w sekwencyjne przejście przez tablicę, co prowadzi do złożoności kwadratowej.

Jednak w średnim i najlepszym przypadku QuickSort działa w O(n log n), co czyni go bardzo wydajnym w praktyce.

Przykład w C# (bez optymalizacji wyboru pivot):

void QuickSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int pivot = arr[right];
    int partitionIndex = left;
    for (int i = left; i < right; i++) {
        if (arr[i] < pivot) {
            int temp = arr[i];
            arr[i] = arr[partitionIndex];
            arr[partitionIndex] = temp;
            partitionIndex++;
        }
    }
    arr[right] = arr[partitionIndex];
    arr[partitionIndex] = pivot;

    QuickSort(arr, left, partitionIndex - 1);
    QuickSort(arr, partitionIndex + 1, right);
}

Jeśli dane wejściowe są już posortowane lub prawie posortowane, a pivot jest źle wybierany (np. zawsze ostatni element), złożoność będzie O(n²).