Sortowanie szybkie (quick sort) to jeden z najpopularniejszych algorytmów sortowania. Działa zgodnie z zasadą dziel i zwyciężaj.
Algorytm wybiera jeden element jako pivot i dzieli tablicę na dwie części:
- elementy mniejsze od pivota,
- elementy większe od pivota.
Następnie rekurencyjnie sortuje obie części.
Schemat działania
[5, 2, 8, 1, 3]
wybierz pivot, np. 3
mniejsze: [2, 1]
pivot: [3]
większe: [5, 8]
Po posortowaniu części wynik to:
[1, 2, 3, 5, 8]
Złożoność
Typowa złożoność czasowa sortowania szybkiego wynosi:
- średnio: O(n log n),
- w najlepszym przypadku: O(n log n),
- w najgorszym przypadku: O(n²).
Najgorszy przypadek może wystąpić, gdy pivot jest wybierany niekorzystnie, np. zawsze jako najmniejszy lub największy element.
Stabilność
W klasycznej implementacji sortowanie szybkie jest niestabilne. Oznacza to, że elementy o tej samej wartości mogą zmienić względem siebie kolejność.
Na egzaminie
Jeżeli pytanie brzmi: „Który algorytm sortowania nie jest stabilny?”, a w odpowiedziach pojawia się sortowanie szybkie, to najczęściej właśnie ono jest poprawną odpowiedzią.