Sortowanie

Cześć mam takie pytanko Jak złożoność obliczeniowa algorytmu sortowania szybkiego zależy od wyboru elementu dzielącego x i od struktury sortowanego ciągu liczb?

Czy to prawda że Polecaną Techniką jest wybieranie środkowego indeksu sortowanej tablicy,żeby osiągnąć złożoność O(log(n)) poziomu wywołań stosu . O(n) to złożoność obliczeniowa która rośnie liniowo a więc jest to przypadek zły pod kątem ilości operacji do wykonania. Wybieranie zawsze skrajnego elementu tablicy daje złożoność obliczeniową O(n^2) , a więc jest to zły wybór pod kątem ilości operacji do wykonania.

I jeszcze jedno pytanko czy Liczba porównań i Liczba przesunięć bądź zamian elementów dla sortowania przez Wybieranie,Sortowania przez Wstawianie i Sortowania bąbelkowego będzie równa (Liczba porównań 45)(Liczba przesunięć 9)

Jeśli się mylę proszę o poprawę :) z góry dziękuję za odpowiedzi

Najlepszy przypadek jest wtedy kiedy zawsze dzielisz tablice na równe połowy +/- 1. Czyli to rzeczywiście będzie środkowy indeks tablicy, tyle że tej już posortowanej. Wybór jednak dokonujemy wcześniej na nie posortowanej tablicy, dlatego lepiej wziąć chociażby 3 indeksy i wybrać z niego ten o wartości środkowej jako pivot (element według którego dzielimy tablice).