Złożoność czasowa i pamięciowa

Złożoność czasowa:

• Przypadek średni: O(n log n)
  • Zrównoważony element osiowy dzieli tablicę mniej więcej na pół za każdym razem, co daje około log n poziomów pracy związanej z podziałem o złożoności O(n).
• Przypadek najgorszy: O(n²)
  • Jeśli element osiowy jest zawsze najmniejszym lub największym elementem (na przykład w już posortowanej tablicy, gdy elementem osiowym jest ostatni element), jedna strona jest za każdym razem pusta, a rekurencja osiąga głębokość n poziomów.

Złożoność pamięciowa:

• O(n) dla wersji, którą tutaj tworzymy, ponieważ na każdym kroku tworzymy nowe, mniejsze i większe listy. Klasyczne sortowanie szybkie w miejscu zmniejsza tę wartość do O(log n) dodatkowej pamięci.

Podsumowanie:

• Sortowanie szybkie jest bardzo szybkie w przypadku średnim i w praktyce jest powszechnie stosowanym algorytmem sortującym.
• Nieodpowiedni wybór elementu osiowego może zwiększyć złożoność do O(n²); dobre strategie wyboru elementu osiowego (takie jak wybór losowego elementu lub mediany) pozwalają tego uniknąć.