Najefektywniejszy algorytm szukający medianę

Odpowiedz Nowy wątek
2018-11-06 22:16
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?

Pozostało 580 znaków

2018-11-06 22:42
2018-11-06 23:59
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.

Pozostało 580 znaków

2018-11-07 07:51
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;
}
edytowany 2x, ostatnio: spamgolden, 2018-11-07 08:23

Pozostało 580 znaków

2018-11-14 14:42
1

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


Jeśli chcesz pomocy, NIE pisz na priva, ale zadaj dobre pytanie na forum.
edytowany 1x, ostatnio: MarekR22, 2018-11-14 14:43

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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