Najefektywniejszy algorytm szukający medianę

0

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?

1

W quick sorcie wybierasz jeden element i dzielisz zbiór na trzy podzbiory, elementów mniejszych, równych i większych.
Tutaj robisz podobnie, z tym że od razu wiesz w którym z tych trzech zbiorów znajduje się mediana (bo znasz rozmiary podzbiorów). Wykonujesz metodę rekurencyjnie na pozostałych liczbach.

0

czyli jeśli np podzbiór elementów większych ma najwięcej liczb to znaczy, że w nim jest mediana?
Wtedy wykonuję znów Quick sort na tym największym podzbiorze?

Napisałem coś takiego, ale wysypuje się...

#include <iostream>
#include <cstdlib>
using namespace std;

PARTITION(int tablica[],int pocz,int kon,int piwot){
int i=pocz, j=kon;
while(1){
while(tablica[i]<piwot)
i++;
while(tablica[j]>piwot)
j--;
if(i>=j)
return j;
swap(tablica[i], tablica[j]);
i++; j--;
}
}

int QUICK_SORT(int tablica[],int pocz,int kon){
int piwot=tablica[kon];

int sr=PARTITION(tablica, pocz, kon, piwot);
if(kon==sr && pocz==sr){
    return sr;
}
if(abs(sr-pocz)>=abs(kon-sr)){
    QUICK_SORT(tablica, pocz, sr);
}
else{

QUICK_SORT(tablica, sr+1, kon);
}
}
int main()
{
    int tab[]={1,2,3};
    int a=QUICK_SORT(tab,0,2);
    cout <<a<< endl;
    return 0;
}

1

Zero sortowania złożoność liniowa:
https://pl.wikipedia.org/wiki/Algorytm_magicznych_pi%C4%85tek

1 użytkowników online, w tym zalogowanych: 0, gości: 1