Strona główna » Algorytmy » Artykuły » Wyszukiwanie Mediany
 

Wyszukiwanie Mediany

https://mattomatti.com/a0047

Szukanie mediany

W celu znalezienia mediany z pewnego zbioru o n elementach należy je posortować w kolejności od najmniejszej do największej. Następnie dla nieparzystej ilości elementów n medianą jest wartość w środku posortowanej tablicy. Jednak dla parzystego n wynikiem jest średnia arytmetyczna dwóch środkowych elementów.

Przykład

Weźmy przykładowo tablicę L:={2, 4, 6, 5, 5, 1, 4, 1, 3}. Pierwszy krok polega na posortowaniu tablicy rosnąco: {1, 1, 2, 3, 4, 4, 5, 5, 6}. Tablica ma nieparzystą liczbę elementów n = 9, więc szukany element znajduje się na pozycji (n + 1)/2 = 5 i jest to wartość 4.

Jednak w przypadku, gdy dana jest lista posortowana {1, 2, 3, 4, 5, 6} i liczba elementów n = 6 jest parzysta to liczymy średnią arytmetyczną elementów środkowych elementów. W tym przypadku jest to (3 + 4)/2 = 3.5.

Implementacja

Do sortowania tablicy można skorzystać z dowolnego algorytmu sortowania. Jednak tutaj zostanie wykorzystany wbudowany algorytm do sortowania.

  1. double mediana(double* tab, int n) {
  2.   sort(tab, tab + n);
  3.   if (n % 2 == 0) {
  4.     return (tab[n / 2 - 1] + tab[n / 2]) / 2;
  5.   } else {
  6.     return tab[(n - 1) / 2];
  7.   }
  8. }

(2.) Na początku należy posortować tablicę, a następnie na podstawie (3.) parzystości ilości elementów w tablicy wybrać poprawną wartość do zwrócenia. Uwaga warto tutaj zauważyć, że elementy w tablicy są indeksowane od zera. Wpływa to na sposób wybierania konkretnych elementów.

Podczas przepisywania powyższej funkcji do obsługi tablic liczb całkowitych należy pamiętać, że zwracana musi być wartość rzeczywista, ponieważ średnia dwóch liczb całkowitych może mieć część ułamkową 0.5.

Testowanie funkcji

W celu przetestowania napisanej funkcji wystarczy przedstawiony fragment kodu.

  1. int main () {
  2.   int n;
  3.   cout << "Podaj ile elementow ma tablica\nn = ";
  4.   cin >> n;
  5.   double* tab = new double[n];
  6.   cout << "Podaj elementy:\n";
  7.   for (int i = 0; i < n; i++)
  8.     cin >> tab[i];
  9.   cout << "Mediana wynosi: " << mediana(tab, n) << endl;
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz funkcję mediana2(), która będzie przyjmować dwie tablice liczb rzeczywistych. Funkcja ma zwracać medianę dwóch tablic. Przykładowo jeśli jedna tablica to L1=[1, 2, 4, 8], a druga L2=[3, 4, 5] to wynikiem jest 4, ponieważ jest to wartosć pośrodku scalonych tablic: L1, 2[1, 2, 3, 4, 4, 5, 8].