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


Question

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;
}

Thanks!!

1
33
12/6/2012 6:10:38 PM

Accepted Answer

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];
    }
  }
}
30
5/25/2018 2:11:04 AM

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.


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon