Cześć mam pytanie jak złozoność obliczeniowa QuickSort zależy od wybory pivota czyli elementu dzielącego X i od struktury sortowanego ciągu ?
0
1
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).
0
Czyli najlepiej wybrać pivota albo jako pierwszy element tablicy albo jako ostatni element tablicy ponieważ będzie mniejszy stos wywołań tak ?
0
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.
0
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 ?
0
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
0
A czy rodzaj uporządkowania początkowego ma wpływ na czas tego sortowania ?
0
"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)
0
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
0
Nie mam takiego programu