Compute Median of Values Stored in Vector - C++

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

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

how to find the median of a vector if the method is const?

Make a copy of myVector, sort it and then calculate the median of that.

We can do a little better than just using std::sort. We don't need to sort the vector completely in order to find the median. We can use std::nth_element to find the middle element. Since the median of a vector with an even number of elements is the average of the middle two, we need to do a little more work to find the other middle element in that case. std::nth_element ensures that all elements preceding the middle are less than the middle. It doesn't guarantee their order beyond that so we need to use std::max_element to find the largest element preceding the middle element.

Another thing that you may not have considered is the case where myVector is empty. Finding the median of an empty vector doesn't really make any sense. For this example, I just used an assert but you might want to throw an exception or something.

double Median::calculate() const {
  assert(!myVector.empty());
  std::vector<double> myVectorCopy = myVector;
  const auto middleItr = myVectorCopy.begin() + myVectorCopy.size() / 2;
  std::nth_element(myVectorCopy.begin(), middleItr, myVectorCopy.end());
  if (myVectorCopy.size() % 2 == 0) {
    const auto leftMiddleItr = std::max_element(myVectorCopy.begin(), middleItr);
    return (*leftMiddleItr + *middleItr) / 2.0;
  } else {
    return *middleItr;
  }
}

Another option is to use a different container to ensure that elements are always sorted. You might consider using std::set. When you insert into an std::set, the set remains sorted so don't have to use std::sort, std::nth_element or std::max_element to find the median. You would get the middle element.

Is there a median function in the C++ library?

There's no need to use a function. To find the median of a list with an odd number of items, just do

cout << sortedArray[size/2];

where sortedArray is the array and size is the size of the array.
For an array with an even number, you should just do something like this

cout << (sortedArray[size/2] + sortedArray[(size/2) - 1])/2

In other words, take the average of the n/2 element and the n/2-1 element.

If you don't know the size, you need to loop through the array and count how many elements there are. Doing it with decimals is irrelevant because the size of an array is always a whole number.

Function to find the median of a vector?

This is wrong because it uses i after making a decision based on n:

        if (ordered[n] > ordered[n + 1]) //if first is greater than second
            {
                temp = ordered[n];  //switch the order of the two values
                ordered[i] = ordered[i + 1];
                ordered[i+1] = temp;

            }

How to sort a vector to find median and mode?

There is a very simple std function that will give you the median of your array: std::nth_element.

Basically, if you want to get your median, you can do this :

std::vector<int> v{5, 6, 4, 3, 2, 6, 7, 9, 3};
std::nth_element(v.begin(), v.begin() + v.size()/2, v.end());
std::cout << "The median is " << v[v.size()/2] << '\n';

This sample is taken directly from the documentation : http://en.cppreference.com/w/cpp/algorithm/nth_element

To find the mode, you could first sort your vector and the traverse the array. This would be in O(nlog(n)) because of the sorting. Since they are sorted, same elements are next to one another so it's easy to see where there is the most replication.

Finding a median of a collection of values in c++

Short of any other specific requirements, you should default to a std::vector. You mention that you want to remove items later; this implies that you may want to consider a std::list instead.

To find the median, you can use std::nth_element, asking it to pivot on the N/2-th (or (N-1)/2-th) element. This runs in O(N) time.

Get Median Element Of Vector Of Strings [C++]

The algorithm you're trying to implement is:

• Read number of tests; ignore the rest of the line.
• For each test
  
  
  • read number of test values, ignore the rest of the line
  • read a single line containing test values
  • split line of tests into value vector
  • sort vector
  • find middle element

You're either failing, or just plain not doing, the bold portions above. For example, your code:

cin >> length; 
string buffer;
while(getline(cin, input))

will read in the formatted length as an integer, but the remainder of the current line (which is likely just a newline) is left in the input stream. Therefore the getline consume that, not the line of test values. Worse, that means all the logic inside the for-loop will be working with an empty input line, which means there will be no values stored in the vector. That means when you get here:

if (v.size() % 2 == 0)
{
    middle = v[v.size()/2 -1];
}

v.size() is zero, which means v.size() % 2 is zero, which means your "middle" is now set to v[-1], which is clearly out of bounds.

So the biggest problem is you're not properly consuming remaining line data after formatted input, a common problem for beginning C++ programmers. See this question and related answers.

The second problem, that while (getline(...)) is wrong. that will consume all data until the end of your file. you only want ONE line of data; not all the remaining lines of data. Once you fix the formatted input problem mentioned prior, that while should be if instead.

Code

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <string>
#include <limits>
#include <iterator>

int main()
{
    unsigned int numberOfExamples;
    if (!(std::cin >> numberOfExamples) || numberOfExamples == 0)
        return EXIT_FAILURE;

    while (numberOfExamples-- > 0)
    {
        unsigned int n_tests = 0;
        if (std::cin >> n_tests)
        {
            if (n_tests == 0)
                continue;

            // consume remainder of test lines
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

            // read set of values
            std::string line;
            if (std::getline(std::cin, line))
            {
                std::istringstream iss(line);
                std::vector<int> v {
                    std::istream_iterator<int>(iss),
                    std::istream_iterator<int>() };

                if (v.size() > 0)
                {
                    std::sort(v.begin(), v.end());

                    if (v.size() % 2 == 0)
                        std::cout << v[v.size()/2-1] << '\n';

                    else
                        std::cout << v[v.size()/2] << '\n';
                }
            }
        }
        else
        {
            std::cerr << "Failed to read number of test values\n";
        }
    }
}

Input

2
5
12 4 22 31 32
8
22 33 44 11 55 66 88 99

Output

22
44

See it live

Finding the median of a vector

A vector's size is simply v.size(), not what you wrote here

int n = sizeof(list1)/sizeof(list1[0]);

This call should be changed from

findMedian(list1, n)

to

findMedian(list1.data(), n)

because a vector is not an array.

Correct these and your code will work.

---

Related Topics