QuickSort - złożoność obliczeniowa

Question

W jaki sposób złożoność obliczeniowa algorytmu QuickSort jest zależna od wyboru elementu dzielącego x oraz od struktury sortowanego ciągu liczb?

Answer 1

Sortowanie szybkie w średnim przypadku ma złożoność O(n log n), a w najgorszym O(n ^ 2). To z jakim przypadkiem mamy do czynienia zależy od elementu osiowego.

Powiedzmy, że kiedy jako element osiowy wybierzesz jakieś X, to znajdziesz blisko połowę wartości mniejszych od X i połowę większych (i tak dla każdego wywołania rekursywnego, aż do przypadku podstawowego). Wtedy dla każdego poziomu musisz przejść przez n elementów, by je ustawić po odpowiedniej stornie osi. Następne wywołanie otrzyma listę o długości n/2 (bo elementy listy rozdzieliły się po połowie wokół osi) itd... Mnożysz O(n) * O(log n) i wychodzi O(n log n).

A co gdybyś po wybraniu osi X miał pecha, bo po lewej stronie znalazła by się tylko jedna liczba, a po prawej wszystkie pozostałe? Przykładem może być następujący ciąg przy założeniu, że zawsze jako oś bierzesz lewą skrajną wartość:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... 1000

Liczba elementów po prawej stronie osi dla następnego wywołania rekurencyjnego nie będzie już o połowę mniejsza, ale mniejsza o zaledwie jeden skrajny element. To ponownie każdy poziom rekurencji przetwarza n liczb. Ponieważ z kolejnymi wywołaniami ciąg jest o zaledwie jeden element krótszy, będziesz miał wysokość stosu wywołań również równą n (a już nie optymistycznie log n). Ponownie mnożysz O(n) * O(n) i otrzymujesz O(n ^ 2).

By tego uniknąć, jako oś należy wybrać losową wartość z sortowanego ciągu.

Answer 2

Przypadek pesymistyczny występuje wtedy, gdy klucz osiowy za każdym razem znajdzie się na brzegu tabeli. Wówczas przy każdym kolejnym wywołaniu liczba elementów do posortowania jest tylko o 1 mniejsza, zatem funkcja zostanie wywołana n razy. Pesymistyczna złożoność czasowa wynosi zatem O(n2).

- to jest dokładnie co kolega powiedział 

Nalezy pamiętać że Wybór klucza osiowego może być dowolny, jednak powinien być jak najszybszy. W praktyce często stosuje się po prostu wybór pierwszego elementu.
Bo to znacznie obniża efektywność