QuickSort a Pivot

Cześć mam pytanie jak złozoność obliczeniowa QuickSort zależy od wybory pivota czyli elementu dzielącego X i od struktury sortowanego ciągu ?

Wybór pivota w sortowaniu szybkim mówi o tym jaki będzie wysokość stosu wywołań. Jeśli ustawisz element osiowy na pierwszy element tablicy, którą chcesz posortować to stos wywołań będzie miał złożoność obliczeniową O(n) w najgorszym przypadku, jeśli elementem osiowym będzie element o indexie środkowym sortowaniem tablicy to wysokość stosu wywołań będzie miała złożoność obliczeniową O(log(n)). Przy czym samo sortowanie zawsze będzie posiadało złożoność obliczeniową O(n) więc sprawa wygląda następująco:

• najgorszy przypadek przy piwocie arr[0] --> O(n^2)
• najgorszy przypadek przy piwocie, który jest za każdym razem indexem środkowym tablicy sortowanej --> O(nlog(n))

Tutaj różnicę robi właśnie ten poziom stosu wywołań, który może się zmieniać w zależności od doboru elementu osiowego -> możesz dzielić cały czas tablice na pół przy ich sortowaniu co daje właśnie O(log(n)) a możesz mieć element osiowy jako skrajny element tablicy wówczas poziom stosu wywołań rośnie liniowo, bo piwot jedynie inkrementujesz a zatem tworzy to złożoność O(n).

Czyli najlepiej wybrać pivota albo jako pierwszy element tablicy albo jako ostatni element tablicy ponieważ będzie mniejszy stos wywołań tak ?

No właśnie odwrotnie. Polecaną techniką jest wybieranie albo losowego albo środkowego indeksu sortowanej tablicy, żeby osiągnąć złożoność O(log(n)) poziomu wywołań stosu. Przecież O(n) to złożoność obliczeniowa, która rośnie liniowo, a więc jest to przypadek dość zły pod kątem ilości operacji do wykonania - oczywiście różnica jest zauważalny przy większych tablicach typu 4 miliardy elementów na przykład.

Dobra dzięki za odpowiedź a mam jeszcze jedno pytanko:

aby obliczyć czas wykonania obliczeń dla QuickSorta dla n=10 w którym uporządkowanie początkowe jest :

niemalejące czyli sortowane ma być od najmniejszej do największej liczby
nierosnące czyli sortowanie ma być od największej do najmniejszej liczby

a co oznacza uporządkowanie początkowe losowe ?

Uporządkowanie początkowe to jest zapewne ułożenie liczb tablicy przekazanej do sortowania, zatem uporządkowanie początkowe losowe oznacza, że tablicy nie jest posortowana przed przetworzeniem jej przez algorytm

A czy rodzaj uporządkowania początkowego ma wpływ na czas tego sortowania ?

"Najprostsza, "naiwna" metoda podziału – wybieranie zawsze skrajnego elementu tablicy – dla danych już uporządkowanych daje katastrofalną złożoność O(n^2)." Oczywiście chodzi tutaj o (poziom wywołań stosu * ilośc operacji potrzebnych do sortowania)

Źródło: https://pl.wikipedia.org/wiki/Sortowanie_szybkie

A masz możne program w c++ przyrównujący procesy wszystkich algorytmów sortowania , mam na myśli taki program w którym podajesz liczbę elementów n a , a po wykonaniu wszystkich porównań algorytm taki wyrzuca ci czas wykonania kodu

Nie mam takiego programu

Żeby zminimalizować szanse na złożonośż kwadratową, standartowo stosuje się "median-of-3" - czyli piwotem jest mediana pierwszego, ostatniego i środkowego elementu (C++ STL). Biblioteki standartowe mają swoje sposoby na optymalizacje sortwania:

• Intorsort - C++, .Net;
• Timsort - Java, Python.