Algorithm for calculating the mode

Question

I am trying to develop an algorithm in the form of a function that takes two parameters, an array and the size of the array. I want it to return an array mode, and if there are several modes, return their average value. My strategy was to take an array and sort it first. Then count all the numbers of the number. while this number occurs, add one to the counter and store this count in array m. So m holds all the counters, and another q array holds the last value that we compared.

For example: my list is {1, 1, 1, 1, 2, 2, 2} then I would have m[0] = 4 q[0] = 1 and then m[1] = 3 and q[1] = 2.

therefore, the mode q[0] = 1;

Unfortunately, I have not yet been successful. hoping someone can help.

 float mode(int x[],int n) { //Copy array and sort it int y[n], temp, k = 0, counter = 0, m[n], q[n]; for(int i = 0; i < n; i++) y[i] = x[i]; for(int pass = 0; pass < n - 1; pass++) for(int pos = 0; pos < n; pos++) if(y[pass] > y[pos]) { temp = y[pass]; y[pass] = y[pos]; y[pos] = temp; } for(int i = 0; i < n;){ for(int j = 0; j < n; j++){ while(y[i] == y[j]) { counter++; i++; } } m[k] = counter; q[k] = y[i]; i--; //i should be 1 less since it is referring to an array subscript k++; counter = 0; } } 

Answer 1

Even if you already have good answers, I decided to post another one. I’m not sure that this really adds much, but I’m not sure that this is not the case either. If nothing else, I'm sure it uses more standard headers than any other answers. :-)

 #include <vector> #include <algorithm> #include <unordered_map> #include <map> #include <iostream> #include <utility> #include <functional> #include <numeric> int main() { std::vector<int> inputs{ 1, 1, 1, 1, 2, 2, 2 }; std::unordered_map<int, size_t> counts; for (int i : inputs) ++counts[i]; std::multimap<size_t, int, std::greater<size_t> > inv; for (auto p : counts) inv.insert(std::make_pair(p.second, p.first)); auto e = inv.upper_bound(inv.begin()->first); double sum = std::accumulate(inv.begin(), e, 0.0, [](double a, std::pair<size_t, int> const &b) {return a + b.second; }); std::cout << sum / std::distance(inv.begin(), e); } 

Compared to @Dietmar's answer, this should be faster if you have many repetitions in numbers, but it will probably be faster if the numbers are mostly unique.

Answer 2

Based on the comment, it seems you need to find the values ​​that occur most often, and if there are several values ​​occurring as many times, you need to produce an average of them. This seems to be easy to do with std::sort() , following the search for a workaround, where the values ​​are changed and several counters are saved:

 template <int Size> double mode(int const (&x)[Size]) { std::vector<int> tmp(x, x + Size); std::sort(tmp.begin(), tmp.end()); int size(0); // size of the largest set so far int count(0); // number of largest sets double sum(0); // sum of largest sets for (auto it(tmp.begin()); it != tmp.end(); ) { auto end(std::upper_bound(it, tmp.end(), *it)); if (size == std::distance(it, end)) { sum += *it; ++count; } else if (size < std::distance(it, end)) { size = std::distance(it, end); sum = *it; count = 1; } it = end; } return sum / count; } 

Answer 3

If you just want to count the number of occurrences, I suggest you use std::map or std::unordered_map .

If you map the counter to each individual value, then it is easy to count the occurrence using std::map , since each key can be inserted once. To list the individual numbers in your list, simply drag around the map.

Here is an example of how you could do this:

 #include <cstddef> #include <map> #include <algorithm> #include <iostream> std::map<int, int> getOccurences(const int arr[], const std::size_t len) { std::map<int, int> m; for (std::size_t i = 0; i != len; ++i) { m[arr[i]]++; } return m; } int main() { int list[7]{1, 1, 1, 1, 2, 2, 2}; auto occurences = getOccurences(list, 7); for (auto e : occurences) { std::cout << "Number " << e.first << " occurs "; std::cout << e.second << " times" << std::endl; } auto average = std::accumulate(std::begin(list), std::end(list), 0.0) / 7; std::cout << "Average is " << average << std::endl; } 

Output:

 Number 1 occurs 4 times Number 2 occurs 3 times Average is 1.42857 

Answer 4

Here is the working version of your code. m stores values ​​in an array, and q stores their number. In the end, he runs through all the values ​​to get the maximum score, the sum of the modes and the number of different modes.

 float mode(int x[],int n) { //Copy array and sort it int y[n], temp, j = 0, k = 0, m[n], q[n]; for(int i = 0; i < n; i++) y[i] = x[i]; for(int pass = 0; pass < n - 1; pass++) for(int pos = 0; pos < n; pos++) if(y[pass] > y[pos]) { temp = y[pass]; y[pass] = y[pos]; y[pos] = temp; } for(int i = 0; i < n;){ j = i; while (y[j] == y[i]) { j++; } m[k] = y[i]; q[k] = j - i; k++; i = j; } int max = 0; int modes_count = 0; int modes_sum = 0; for (int i=0; i < k; i++) { if (q[i] > max) { max = q[i]; modes_count = 1; modes_sum = m[i]; } else if (q[i] == max) { modes_count += 1; modes_sum += m[i]; } } return modes_sum / modes_count; }