Po ilu podziałach w quicksorcie można policzyć medianę


(MrGalek) #1

Hej
Mam pytanie mianowicie w przykładowym zadaniu na koło z Algorytmów jest zadanie: Dla liczb {3,14,15,6,2,11,8,19,21} określ po ilu podziałach znajdzie się medianę. Jakim algorytmem (O(nlgn)). Algorytm to wiem że będzie quicksort ale nie wiem jak ma ta mediana wyglądać.

PS:
Wiem że regulamin nie pozwala na rozwiązywanie prac domowych. To nie jest PD, tylko przykładowe zadanie, nie chce też gotowca tylko w miarę powiedzenie jak to działa. Nawet inne liczby mogą być, nie zalezy mi na typowej odpowiedzi tylko ogólnym mechanizmie.
Z góry dziękuję
MrGalek


(MrGalek) #2

Jakby jakiś dziki student potrzebował to, trzeba ogarnąć Algorytm Hoare’a