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

Wyszukiwanie Mediany

Obliczanie 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.

Prosta Implementacja

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

  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. Najpierw wczytuje od użytkownika rozmiar wprowadzanej tablicy, a następnie jej poszczególne elementy.

  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 miała nagłówek:

  1. double mediana2(double* tab, int n, double* tab2, int n2) {

Jej działanie ma polegać na zwróceniu mediany elementów z pierwszej tablicy tab oraz drugiej tab2.