Pytanie 1
Jakie sformułowanie najlepiej oddaje złożoność obliczeniową algorytmu quicksort?
A. jest większa niż złożoność sortowania bąbelkowego
B. jest różna w zależności od wyboru elementu dzielącego
C. jest zawsze mniejsza niż złożoność jakiegokolwiek innego algorytmu sortowania
D. jest większa niż O(n2)
Quicksort to jeden z najszybszych i najczęściej stosowanych algorytmów sortowania, ale jego złożoność obliczeniowa nie jest stała i zależy od wyboru elementu rozdzielającego (pivot). W najgorszym przypadku, gdy pivot wybierany jest niefortunnie (np. największy lub najmniejszy element), złożoność quicksort wynosi O(n²). W przypadku optymalnym (pivot dzieli zbiór na dwie równe części), złożoność to O(n log n). Algorytm ten działa w sposób rekurencyjny, dzieląc tablicę na mniejsze podzbiory, co czyni go bardzo efektywnym dla dużych zbiorów danych. W praktyce quicksort jest często szybszy niż sortowanie przez scalanie (merge sort) ze względu na mniejszą liczbę operacji przesuwania danych, mimo że oba algorytmy mają podobną średnią złożoność obliczeniową.
