Pivot to element dzielący używany w algorytmie quicksort. Na jego podstawie tablica jest dzielona na dwie części: elementy mniejsze od pivota oraz elementy większe od pivota. Następnie te części są sortowane rekurencyjnie.
Dlaczego pivot jest ważny?
Wybór pivota bezpośrednio wpływa na złożoność obliczeniową quicksorta. Jeśli pivot dzieli dane mniej więcej na połowy, algorytm działa bardzo szybko. Jeśli jednak pivot jest stale elementem najmniejszym lub największym, podział jest skrajnie nierówny.
Typowe przypadki złożoności
- przypadek optymistyczny:
O(n log n)— pivot dzieli tablicę prawie równo, - przypadek średni:
O(n log n)— dla losowych danych lub dobrego wyboru pivota, - przypadek pesymistyczny:
O(n²)— pivot powoduje bardzo nierówne podziały.
Przykład złego wyboru pivota
Jeśli jako pivot zawsze wybierany jest pierwszy element, a tablica jest już posortowana, np.:
[1, 2, 3, 4, 5]
pivot 1 nie podzieli danych równomiernie. Jedna część będzie pusta, a druga będzie zawierała prawie wszystkie pozostałe elementy. Taka sytuacja prowadzi do złożoności O(n²).
Jak poprawia się wybór pivota?
Często stosuje się:
- wybór losowego elementu jako pivota,
- wybór środkowego elementu,
- metodę „mediana z trzech” — wybór mediany spośród pierwszego, środkowego i ostatniego elementu.
W pytaniach egzaminacyjnych najważniejsze jest zapamiętanie, że złożoność quicksorta nie jest stała dla każdego przypadku i zależy m.in. od wyboru elementu dzielącego.