Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Compute Median of Values Stored In Vector - C++?

Tags:

c++

vector

median

I'm a programming student, and for a project I'm working on, on of the things I have to do is compute the median value of a vector of int values. I'm to do this using only the sort function from the STL and vector member functions such as .begin(), .end(), and .size().

I'm also supposed to make sure I find the median whether the vector has an odd number of values or an even number of values.

And I'm Stuck, below I have included my attempt. So where am I going wrong? I would appreciate if you would be willing to give me some pointers or resources to get going in the right direction.

Code:

int CalcMHWScore(const vector<int>& hWScores) {      const int DIVISOR = 2;      double median;      sort(hWScores.begin(), hWScores.end());      if ((hWScores.size() % DIVISOR) == 0)      {          median = ((hWScores.begin() + hWScores.size()) + (hWScores.begin() + (hWScores.size() + 1))) / DIVISOR);      }      else       {        median = ((hWScores.begin() + hWScores.size()) / DIVISOR)      }      return median; } 
like image 335
Alex Avatar asked Jan 22 '10 03:01

Alex


People also ask

How do you find the median of a vector?

Median of a vector is the central tendency of elements in the vector. Median is calculated by arranging items of a vector in ascending and descending order, and the item that is in the middle of the sorted vector is our median.

How do you find the median of an even number in C?

Odd numbers of items have just one middle value whereas; even numbers of items have two middle values. The median for even number of items is therefore, designated as the average of the two middle values.


2 Answers

There is no need to completely sort the vector: std::nth_element can do enough work to put the median in the correct position. See my answer to this question for an example.

Of course, that doesn't help if your teacher forbids using the right tool for the job.

like image 69
Mike Seymour Avatar answered Sep 21 '22 14:09

Mike Seymour


You are doing an extra division and overall making it a bit more complex than it needs to be. Also, there's no need to create a DIVISOR when 2 is actually more meaningful in context.

double CalcMHWScore(vector<int> scores) {   size_t size = scores.size();    if (size == 0)   {     return 0;  // Undefined, really.   }   else   {     sort(scores.begin(), scores.end());     if (size % 2 == 0)     {       return (scores[size / 2 - 1] + scores[size / 2]) / 2;     }     else      {       return scores[size / 2];     }   } } 
like image 42
Max Shawabkeh Avatar answered Sep 24 '22 14:09

Max Shawabkeh