Cześć,
Analizuje algorytm szybkiego sortowania - wersje, gdzie zawsze porównuje z pierwszym elementem.
Myślałem, że najoptymalnym przypadkiem będzie ciag uporzadkowany, ale okazala sie ze randomowy jest zdecydowanie lepszym...
0
3
Ta, quick sort jest o tyle nietypowym przypadkiem, że jemu uporządkowanie tablicy nie tylko nie pomaga, ale wręcz szkodzi — sortowanie już uporządkowanej kolekcji jest jego najgorszym przypadkiem.
Najlepszy, natomiast, jest wtedy, kiedy każdy z podziałów dzieli nam tablicę na równe części, bo to nam redukuje problem możliwie mocno — ostatecznie, będzie potrzebne tylko log(n) przebiegów¹. Będzie tak wtedy, kiedy pivot jest medianą szukanego przedziału.
¹ Każdy o złożoności liniowej, więc n log (n) ostatecznie na całość.
0
Zobacz na ten wątek:
https://stackoverflow.com/questions/7559608/median-of-three-values-strategy