Skip to content

Instantly share code, notes, and snippets.

@lawliet89
Created November 13, 2012 00:11
Show Gist options
  • Save lawliet89/4062966 to your computer and use it in GitHub Desktop.
Save lawliet89/4062966 to your computer and use it in GitHub Desktop.
Mean, Median, Mode
// Mean medium and mode
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <map>
using namespace std;
// This is a variant of merge sort that does mode counts and sums all the items.
template <typename InputIterator, typename OutputIterator, typename ValueType, typename SumType> void mergesort(InputIterator start, InputIterator end, OutputIterator output, SumType &sum, map<ValueType, int> &mode){
int size = end-start;
if (size == 1){
// Oh, base case
*output = *start;
// OK onward to our mean and mode calculation
sum += *start;
if (mode.find(*start) == mode.end()){
mode[*start] = 1;
}
else
mode[*start]++;
return;
}
// Split
int split = size/2;
// Sort Left
mergesort(start, start+split,output, sum, mode);
// Sort Right
mergesort(start+split, end, output+split, sum, mode);
// Merge in place - O(n)
inplace_merge (output, output+split, output+size);
}
bool modeCompare(pair<int, int> left, pair<int, int> right){
return left.second < right.second;
}
int main (){
const int count = 21;
int input[] = {5,10,15,20,25,50,40,30,20,10,9524,878,17,1,-99,18785,3649,-3,164,94, 10};
int *output; // Sorted array
map<int, int> modeCount;
long sum = 0;
output = new int[count];
mergesort(input, input+count, output, sum, modeCount);
// Mean
int mean = (int) ( sum / (long) count );
int median;
//Get median
if (count % 2 == 0){
median = (input[count/2] + input[count/2 - 1])/2;
}
else{
median = input[count/2];
}
// o(n)
map<int, int>::iterator mode = max_element(modeCount.begin(), modeCount.end(), modeCompare);
cout << "Mean: " << mean << endl;
cout << "Median: " << median << endl;
cout << "Mode: " << (*mode).first << endl;
delete[] output;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment