'C++ Calculating the Mode of a Sorted Array
I have to write a C++ code that finds the median and mode of an array. I'm told that it's much easier to find the mode of an array AFTER the numbers have been sorted. I sorted the function but still cannot find the mode.
int counter = 0;
for (int pass = 0; pass < size - 1; pass++)
for (int count = pass + 1; count < size; count++) {
if (array [count] == array [pass])
counter++;
cout << "The mode is: " << counter << endl;
Solution 1:[1]
If the array has been sorted already, you can count the occurrences of a number at once. Then just save the number that has biggest occurrences. And you can find out the mode in only one for-loop. Otherwise, you'll have to do more than one for-loops. See a details example at the link below Find-the-Mode-of-a-Set-of-Numbers
Here is the code,
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // count occurrences of the current number
++count;
}
else
{ // now this is a different number
if (count > countMode)
{
countMode = count; // mode is the biggest ocurrences
mode = number;
}
count = 1; // reset count for the new number
number = array[i];
}
}
cout << "mode : " << mode << endl;
Solution 2:[2]
One way is that you can use Run Length encoding. In Run Length encoding, representation would be like; (Item, Its frequency).
While doing so, keep track of the maximum frequency and Item. This will give you the mode once you complete the Run Length.
for example:
1 1 2 2 2 3 3 4 5
It run length encoding would be
{1, 2}, {2, 3}, {3, 2}, {4, 1}, {5, 1}
It needs O(n) space.
Solution 3:[3]
This is how I did it, my solution will take a sorted vector as input. It has O(n) time complexity and can work with the case where there are more than 1 "mode" number in the vector.
void findMode(vector<double> data) {
double biggestMode = 1;
vector<double> mode, numbers;
numbers.push_back(data.at(0));
mode.push_back(1);
int count = 0;
for (int i = 1; i < data.size(); i++) {
if (data.at(i) == numbers.at(count)) {
mode.at(count)++;
}
else {
if (biggestMode < mode.at(count)) {
biggestMode = mode.at(count);
}
count++;
mode.push_back(1);
numbers.push_back(data.at(i));
}
}
for (int i = 0; i < mode.size(); i++) {
if (mode.at(i) == biggestMode)
cout << numbers.at(i) << " ";
}
cout << endl;
}
Solution 4:[4]
Here is the code snippet:
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{
count++;
}
else
{
if (count > countMode)
{
countMode = count;
mode = number;
}
count = 1;
number = array[i];
}
}
cout << "mode : " << mode << endl;
Solution 5:[5]
There is an old adage that states "If you put 10 programmers in a room and give them the same program to code you will get 12 different results", hence my version of answering your question. It may not be as fast (I'm planning on testing it's speed versus some of the other suggestions) but I feel it is easy to understand.
#include <iostream>
using namespace std;
int main ()
{
short z[10];
short maxCount = 0, curCount = 0, cur = 0, most = 0;
for (int i = 0; i < 10; i++)
{
cout << "Enter a number: " << endl;
cin >> z[i];
}
for (int i = 0; i < 10; i++)
{
cur = z[i];
for (int a = i; a < 10; a++)
{
if (cur == z[a])
{
curCount++;
cur = z[a];
}
if (curCount > maxCount)
{
maxCount = curCount;
most = z[a];
}
}
curCount = 0;
}
cout << "the mode is : " << maxCount << ", the number is: " << most << endl;
}
Solution 6:[6]
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // count occurrences of the current number
++count;
}
else
{ // now this is a different number
count = 1; // reset count for the new number
number = array[i];
}
if (count > countMode) {
countMode = count;
mode = number;
}
}
cout << "mode : " << mode << endl;
Solution 7:[7]
The "mode" is the value that occurs most often. If no number is repeated, then there is no mode for the list. So there would be no benefit to sorting if you needed to know the "mode".
Are you sure you are not referring to the median? The median is the middle number in a set. If you have 1,2,3,4,5 the Median (middle number) is the (total_number)/2) rounded up if it is odd, 2.5 -> 3 and our median would be 3. you can only really calculate the median if your numbers are sorted. If you have an even number in a set 1,2,3,4,5,6 your mode is slots 3,4 (coincidentally also, 3,4) (total_number)/2 slot and (total_number)/2 + 1 slot, for any even array of numbers.
Solution 8:[8]
This code should give you the mode. If there are equal number of two different numbers, it will output the first of such.
int count = 1, mode = 0, m = 0, i = 1;
size_t sz = sizeof(array)/sizeof(*array);
while(i != sz+1) {
if(array[i-1] != array[i]) {
if(count > m) {
mode = array[i-1];
m = count;
count = 1;
}
}
else
++count;
++i;
}
std::cout << "mode: " << mode << std::endl;
Solution 9:[9]
This code finds the mode in C++:
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
int i,j,k=0,n,repeat_max=0,cn=0;
int array1[50],mode[50],count[50]={0},c[50];
cout<<"\n inter count:\t";
cin>>n;
cout<<"\n";
for(i=0;i<n;i++)
cin>>array1[i];
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(array1[i]==array1[j])
{
count[i]++;
if(count[i]>=repeat_max)
{
repeat_max=count[i];
mode[k++]=array1[i];
}
}
}
}
cout<<"\n================\n";
for(i=1;i<k;i++)
cout<<"\t mode[i]="<<mode[i]<<"\n";
cout<<"\t\n\nrepeat array:"<<repeat_max;
return 0;
}
Solution 10:[10]
I did it this way:
int main()
{
int mode,modecount2,modecount1;
bool is_nomode=false;
vector<int> numbers = { 15,43,25,25,25,25,16,14,93,93,58,14,55,55,55,64,14,43,14,25,15,56,78,13,15,29,14,14,16 };
sort(numbers);
//If you uncomment the following part, you can see the sorted list of above numbers
//for (int i = 0; i < numbers.size(); ++i) std::cout << numbers[i] << '\n';
//keep_window_open();
mode = numbers[0];
modecount1 = 0;
modecount2 = 1; //Obviously any number exists at least once!
for (int i = 1; i < numbers.size(); ++i) {
if(numbers[i]==numbers[i-1]) ++modecount2;
else {
if (modecount2 > modecount1) {
mode = numbers[i - 1];
modecount1 = modecount2;
}
else if (i != 1 && modecount2 == modecount1) { std::cout << "No mode!\n"; is_nomode = true; break; }
modecount2 = 1;
}
}
if(!is_nomode) std::cout << "Mode of these numbers is: " << mode << std::endl;
keep_window_open();
Also you can add another 25 to the list of numbers and see what happens if two numbers have the same occurrence! I hope it helps.
Solution 11:[11]
This code uses "map" to find out the MODE from the given array. It assumes the array is already sorted.
int findMode(int * arr, int arraySize)
{
map<int, int> modeMap;
for (int i = 0; i < arraySize; ++i) {
++modeMap[arr[i]];
}
auto x = std::max_element(modeMap.begin(), modeMap.end(),
[](const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second; });
return x->first;
}
Solution 12:[12]
While Diedrei's answer is close, several people have pointed out some shortcomings such as if the mode is defined by the last numbers of the sorted array (1,2,3,3,4,4,4 would return 3 as the mode). Also, depending on the requirements on how to handle multiple modes, there will be different solutions.
This solution does several things:
- Solves the issue of the mode being at the end of the array
- If there are multiple modes (more than 1 number has the same number of occurrences with a count > 1), returns the smallest number as the mode
- Returns
-1if there is no mode (each number only occurs once)
int number = array[0];
int mode = number;
int count = 1;
int countMode = 1;
for (int i=1; i<size; i++)
{
if (array[i] == number)
{ // increment the count of occurrences for the current number
++count;
if (count > countMode)
{
countMode = count; // this number now has the most occurrences
mode = number; // this number is now the mode
}
}
else
{ // now this is a different number
count = 1; // reset count for the new number
number = array[i]; // set the new number
}
}
if (countMode == 1) {
mode = -1; // set the mode to -1 if each number in the array occur only once
}
cout << "mode : " << mode << endl;
Solution 13:[13]
This is the code I've written for sorted vector
void print_mode(vector<int>& input)
{
int mode=0, count = 0;
int current_number = input[0];
int mode_number = current_number;
for (int i=0; i < input.size(); i++)
{
if (current_number == input[i])//check if the number is the same
{
count++;
}
else //this fuction works when the value are no longer the same and
//this is when it updates the mode value
{
if (count > mode)//update mode value
{
mode = count;
mode_number = current_number;
}
count = 1;// it is not reset back to zero because when it the program detect a
//different number it doesn't count it so this is to solve that issue
}
if (i == input.size() - 1)// this function before it doesn't work when the largest value
//is mode so I added this if state to solve it
{
if (count > mode)
{
mode = count;
mode_number = current_number;
}
}
current_number = input[i];//prepare for next value
}
cout << mode_number << " is the mode number and it is repeated " << mode << " times" << endl;
}
Solution 14:[14]
1. Finding the mode without sorting
I'm told that it's much easier to find the mode of an array AFTER the numbers have been sorted
I'm not so sure.
std::vector<std::pair<int, unsigned>> mode(const std::vector<int> &v)
{
if (v.empty())
return {};
std::unordered_set<int> seen;
unsigned max_count(0);
std::vector<std::pair<int, unsigned>> ret;
for (auto i(v.begin()); i != v.end(); ++i)
if (seen.find(*i) == seen.end())
{
const auto count(std::count(i, v.end(), *i));
if (count > max_count)
{
max_count = count;
ret = {{*i, max_count}};
}
else if (count == max_count)
ret.emplace_back(*i, max_count);
seen.insert(*i);
}
return ret;
}
The algorithm
- uses a hash table (
seen) to skip already seen numbers; - doesn't need a copy of the input vector;
- only requires a container with forward iterator support.
Also note that for small input vectors the function can be simplified removing the hash table.
You can play with the code here.
2. Finding the mode sorting
std::vector<std::pair<int, unsigned>> mode(std::vector<int> v)
{
if (v.empty())
return {};
std::sort(v.begin(), v.end());
auto current(*v.begin());
unsigned count(1), max_count(1);
std::vector<std::pair<int, unsigned>> ret({{current, 1}});
for (auto i(std::next(v.begin())); i != v.end(); ++i)
{
if (*i == current)
++count;
else
{
count = 1;
current = *i;
}
if (count > max_count)
{
max_count = count;
ret = {{current, max_count}};
}
else if (count == max_count)
ret.emplace_back(current, max_count);
}
return ret;
}
We assume an unsorted input vector, so the function works on a copy of the original vector that is sorted and processed.
If the original vector is already sorted, the input argument can be passed by reference and the std::sort call can be removed.
You can play with the code here.
Performance
Performance depends on multiple factor (size of the input vector, distribution of values...).
E.g. if the range of the input integers is small algorithm 1 is faster than algorithm 2.
You can experiment here.
Solution 15:[15]
I know the question is old, but here is a clean and short code that calculates statistical mode:
std::sort(vector.begin(), vector.end());
int mode = vector[0], count = 0, countMode = 1;
int last = mode;
for (int i = 1; i < vector.size(); ++i)
{
if (vector[i] == mode) ++countMode;
else
{
if (last != vector[i]) count = 0;
++count;
}
if (count > countMode)
{
mode = vector[i];
countMode = count;
count = 0;
}
last = vector[i];
}
Solution 16:[16]
This had worked.
int vals[9];
sort(vals, vals + 9);
int key = vals[0], value = 1,max_key=0,max_value=0;
for (int l = 1; l < 9; l++){
if (key == vals[l]){
value++;
}
else{
if (value>max_value){
max_key = vals[l-1];
max_value = value;
}
key = vals[l];
value = 1;
}
}
cout<< "Mode: "<< max_key << endl;
Solution 17:[17]
int findModa(int *arr, int n) {
int count=1;
int countmax=0;
int current = arr[0];
int moda = 0;
for (int i=1; i<n; i++) {
if(arr[i] == curr) {
count++;
}
else if (count>countmax) {
countmax=count;
count=1;
moda=arr[i-1];
current=arr[i];
}
current=arr[i];
}
return moda;
}
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow