Które określenie najlepiej opisuje złożoność obliczeniową algorytmy quicksort?

Poprawna odpowiedź: D

Uzasadnienie i szersze wyjaśnienie:

Quicksort (sortowanie szybkie) jest algorytmem działającym na zasadzie „dziel i zwyciężaj”. Jego wydajność jest silnie uzależniona od sposobu wyboru elementu rozdzielającego (piwota), który służy do podziału tablicy na dwie części.

• Średni i najlepszy przypadek: Jeśli piwot jest wybierany w taki sposób, że dzieli tablicę na w miarę równe części, złożoność obliczeniowa wynosi O(n log n), co jest bardzo wydajne.
• Najgorszy przypadek: Jeśli piwot jest wybierany skrajnie źle (np. zawsze najmniejszy lub największy element w już posortowanej tablicy), podziały są bardzo nierówne, a złożoność algorytmu degraduje do O(n²).

Zatem stwierdzenie, że złożoność jest różna w zależności od wyboru elementu rozdzielającego, najdokładniej opisuje charakterystykę tego algorytmu.

Dlaczego pozostałe odpowiedzi są nieprawidłowe?

• A: W średnim przypadku złożoność Quicksort (O(n log n)) jest znacznie niższa (lepsza) niż złożoność sortowania bąbelkowego (O(n²)).
• B: To nieprawda. Istnieją algorytmy, które w pewnych warunkach są szybsze (np. sortowanie przez zliczanie o złożoności O(n)), a sortowanie przez scalanie ma gwarantowaną złożoność O(n log n), co jest lepsze niż najgorszy przypadek Quicksort.
• C: Złożoność Quicksort nigdy nie jest wyższa niż O(n²).