how to find ''median'' in a list?

[ragecraze]

Hi guys, this is my second week learning c++ and i am really lost at this one: i want to make the program print out the median of the sorted list that i made. That means i want to make an iterator that goes through the list, sorts it from smallest to biggest number, find the middle number and prints it out. Where do i begin? much appriciated.

 
#include <iostream>
#include <list>
#include <map>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    std::list<int> mylist;
    std::list<int>::iterator it;
    int myInt, t;
    double average;


    int sum = 0;


    std::cout << "Please enter some integers (enter 0 to end):\n";


    do {
        std::cin >> myInt;

        if (myInt == 0)
            break;


        mylist.push_back(myInt);

        sum += myInt;


    } while (myInt);


  //  std::cout << "mylist contains:";
  //  for (it=mylist.begin(); it!=mylist.end(); ++it)
  //      std::cout << ' ' << *it;

  //  std::cout << '\n';


    mylist.sort();      // sorting the list from smallest to biggest number
    mylist.reverse();  //  reversing the list to make it sort from biggest to smallest number

    average = sum / mylist.size();



    std::cout << "Average : " << average << "\n";


    std::cout << "Descending : ";
    for (it=mylist.begin(); it!=mylist.end(); ++it)     // printing out the list in descending order (big to small)
        std::cout << ' ' << *it;





    std::cout << '\n';
    return 0;

}

[ragecraze]

could you please specify what you mean?

[cire]

As is his wont, gentleguy is providing wrong information. It is best to just ignore him.

You'll be wanting to use std::list::sort to sort the list. Getting the median from there should be pretty straight forward.

http://en.cppreference.com/w/cpp/container/list/sort

[boost lexical cast]

I am also making a test program that finds mean, median, mode. But instead of using functions to put the numbers in order I am doing it manually with this logic:

Go through all the numbers two at a time. And check if the first number out of those 2 is greater than the second one. If so then switch places of the 2 numbers (I'm using arrays). Move on and keep repeating until they are in order.
Example: 1 & 2, 2 & 3, 3 & 4, etc.

You're probably better off using the sort function but if for some reason it doesn't work you can always use my method.

[mpark4656]

You're probably better off using the sort function but if for some reason it doesn't work you can always use my method.

std::list::sort suggested by cire works. There is no question about that. Just like many std functions, it's a pre-written function that's already been debugged and freely available for you to use and, by all means, take advantage of it. Of course, if you want to learn the sorting algorithm, then feel free to create your own function for sorting and that's perfectly fine as well.

I'm looking at ragecraze's first post and it looks like he already figured out how to sort the list (unless he edited his code after cire's post). Look at line 44 ...
mylist.sort(); // sorting the list from smallest to biggest number

So, I guess his question now is what to do after sorting.

Here are the steps for finding a median
1. Put all the values in numerical order. (Done)
2. If there is an odd number of results, the median is the middle number.
3. If there is an even number of results, the median will be the mean of the two central numbers.

Algorithm for finding median depends on whether n is odd or even (Here, n is the total number of values in the list). Personally, I think vector is better suited for finding a median. You should know that while inserting and removing element with std::list is constant time, it has a linear access time. Finding the median involves finding the nth element in a container and std::vector does a much better job of it than std::list.

Because you are using std::list, you have to start from begin() or end() and traverse each element until you reach the middle element.

So, for std::list, you can do the following. I wonder if there is a better way to get nth element in std::list?

    // Median is double type because for even n, median is the average of 2 central values
    double median;
    auto itr = mylist.begin();

    // n is even
    if( mylist.size() % 2 == 0 ) {
        for( int i = 0 ; i < mylist.size() / 2 ; i ++ ) {
            itr++;
        }

        median = ( (double)*itr + *--itr ) / 2;
    }
    // n is odd
    else {
        for( int i = 0 ; i < mylist.size() / 2 ; i ++ ) {
            itr++;
        }

        median = *itr;
    }