Sortowanie szybkie (Quicksort)

Zasada działania Quicksort:

Quicksort wybiera element osiowy (pivot), a następnie dzieli tablicę na dwie podtablice:

1. Elementy mniejsze lub równe pivotowi (po lewej stronie),
2. Elementy większe od pivota (po prawej stronie). Następnie rekurencyjnie sortuje obie podtablice aż do osiągnięcia podtablic 1-elementowych.

void quickSort(int tab[], int lewy, int prawy) {
    if (lewy >= prawy) return;
    int pivot = tab[(lewy + prawy) / 2];
    int i = lewy, j = prawy;
    while (i <= j) {
        while (tab[i] < pivot) i++;
        while (tab[j] > pivot) j--;
        if (i <= j) {
            std::swap(tab[i], tab[j]);
            i++; j--;
        }
    }
    quickSort(tab, lewy, j);
    quickSort(tab, i, prawy);
}

Złożoność Quicksort:

• Średnia złożoność czasowa: O(n log n) – w praktyce jeden z najszybszych algorytmów ogólnego przeznaczenia.
• Pesymistyczna złożoność czasowa: O(n²) – występuje przy skrajnie niekorzystnym doborze pivota (np. zawsze najmniejszy element w posortowanej tablicy).
• Złożoność pamięciowa: O(log n) (na ramki stosu wywołań rekurencyjnych).