QuickSort to algorytm sortowania oparty na metodzie dziel i zwyciężaj. Oznacza to, że problem sortowania całej tablicy jest dzielony na mniejsze podproblemy, które są rozwiązywane niezależnie.
Zasada działania
QuickSort wykonuje trzy główne kroki:
- Wybiera element zwany pivotem.
- Dzieli tablicę na dwie części:
- elementy mniejsze od pivota,
- elementy większe od pivota. - Rekurencyjnie sortuje obie części.
Po zakończeniu działania wszystkie elementy są uporządkowane.
Przykład działania
Dla tablicy:
[8, 3, 5, 1, 9]
Jeśli pivotem będzie 5, tablica zostanie podzielona na:
- mniejsze:
[3, 1] - pivot:
[5] - większe:
[8, 9]
Następnie części [3, 1] oraz [8, 9] są sortowane osobno.
Złożoność obliczeniowa
- średni przypadek: O(n log n),
- najlepszy przypadek: O(n log n),
- najgorszy przypadek: O(n²).
Najgorszy przypadek może wystąpić, gdy pivot jest wybierany bardzo niekorzystnie, np. zawsze jako najmniejszy lub największy element.
Dlaczego QuickSort pasuje do „dziel i zwyciężaj”?
Ponieważ algorytm dzieli tablicę na mniejsze fragmenty, sortuje je osobno, a następnie uzyskuje rozwiązanie całego problemu. W pytaniach egzaminacyjnych QuickSort jest typowym przykładem algorytmu sortowania wykorzystującego tę metodę.