Zaproponuj możliwie efektywny algorytm wyznaczania mediany w zbiorze n liczb rzeczywistych.
Wskazówka: zmodyfikuj algorytm quick sort.
Moje rozwiązanie:
Znalazłem banalne rozwiązanie,
Czyli posortowanie np QuickSortem tego zbioru liczb i później wybranie:
dla nieparzystych n, środkowej komórki tablicy
dla parzystych n, średnią 2 środkowych komórek.
wtedy złożoność będzie O(n*log n). Zapewnie nie o to chodzi w zadaniu. Dacie jakieś wskazówki?