# Is this a good way to calculate the mode of a set of ints?

Today was my first day of Data Structures and Algorithms in C++. We used C# last semester and C++ for the intro class so to get us used to C++ again we had a simple assignment to write a program to read in a file full of ints, print them in reverse order, and then calculate the median and the mode of the set.

At first I struggled with figure out a way to calculate the Mode. It seemed so simple but I just couldn't translate the steps into code. I did come up with a solution and it works but because of my struggle at first I just wanted to get some feedback on if this was a good method or if there's better ways to do it.

``````#include <iostream>             //IO to the screen
#include <fstream>              //File IO
#include <string>               //String manipulation

using namespace std;

/*CONSTANTS*/
const int MAX_ELEMENTS = 100;
const string FILENAME = "data.dat";

/*TYPEDEFS*/
typedef int IntArr[MAX_ELEMENTS];       //data type for an integer array of 100 elements.

/*PROTOTYPES*/
void Print(const IntArr& outArr, int numFilled);        //Prints the array in reverse order.
void Sort(IntArr& outArr, int numFilled);
int CalcMode(const IntArr& numArr, int numFilled);

void main()
{
/*VARIABLES*/
IntArr numArr;          //Holds the integers read in from the file.

ifstream din;
din.open(FILENAME.c_str());

//The file exists.
if(!din)
{
cout << "ERROR: \"" << FILENAME << "\" not found. Program terminating." << endl;
abort();
}//End file exists check
int ind = 0; //The current index of the array to write to.

int num;
din >> num;
//While the last read was successfull
while(din)
{
//Place the num into the array, increment the index counter, and read the next int.
numArr[ind] = num;

ind++;

din >> num;
} //End while loop

Print(numArr, ind);

Sort(numArr, ind);

int median = (ind - 1) / 2;

cout << endl << "Median: " << numArr[median] << endl;

cout << "Mode: " << numArr[ CalcMode(numArr,ind) ] << endl;
} //End main method.

//Pre: outArr has been filled with integers from the file specified and numFilled is the number of filled indices.
//Post: outArr has been output to the screen in reverse order..
//Purpose: Print out the contents of an array to a screen in reverse order.
void Print(/*IN*/const IntArr& outArr,          //Array to be printed
/*IN*/int numFilled)                 //Number of filled indices
{
//Iterate through the array in reverse order and output to the screen.
for(int i = numFilled - 1; i >= 0; i--)
{
cout << outArr[i] << endl;
}//End for loop
}//End Print()

//Pre: The array has been loaded with data from a file.
//Post: The array has been sorted.
//Purpose: To bubble sort the array.
void Sort(/*IN*/ IntArr& outArr,        //Array to be sorted
/*IN*/ int numFilled)         //number of filled indicies in the array
{
//Bubble sort because there's so few elements in the array... and I'm lazy.

bool sorted = false;
//Use a test flag to determine if the array is sorted.
//If not, continue looping
while(!sorted)
{
sorted = true;
//Iterate through every item in the array excluding the last.
for(int i = 0; i < numFilled - 1; i++)
{
//Check to see if the current num is larger than the next.
if(outArr[i] > outArr[i+1])
{
int temp = outArr[i];
outArr[i] = outArr[i+1];
outArr[i+1] = temp;
sorted = false;
}//End If
}//End For
}//End While
}//End Sort()

//Pre: The array passed in should already be sorted.
//Post: Returns the number that occurs the most.
//Purpose: Determine which number occurs most often in a sorted array.
int CalcMode(/*IN*/ const IntArr& numArr,       //Sorted array to calculate the mode for.
/*IN*/ int numFilled)                  //Number of filled indices.
{
int modeArr[MAX_ELEMENTS][1];

//Initialize the int in the second dimension of every element.
for(int i = 0; i < MAX_ELEMENTS; i++)
modeArr[i][0] = 0;

//Count the number of occurences for each number in the array
for(int i = 0; i < numFilled - 1; i++)
modeArr[ numArr[i] ][0]++;

int modeInd = 0;

//Iterate through each index and find out what number had the most occurences.
for(int i = 0; i < numFilled - 1; i++)
{
if(modeArr[ numArr[i] ][0] > modeArr[ numArr[modeInd] ][0])
{
modeInd = i;
}//End if
}//End for

return modeInd;
}//End CalcMode();
``````

EDIT: I took Useless' useful advice and instead of populating a secondary array I just iterated through the sorted array and calculated run lengths. Here's the code I came up with for that:

``````//Pre: The array passed in should already be sorted.
//Post: Returns the number that occurs the most.
//Purpose: Determine which number occurs most often in a sorted array.
int CalcMode(/*IN*/ const IntArr& numArr,       //Sorted array to calculate the mode for.
/*IN*/ int numFilled)                  //Number of filled indices.
{
int modeInd = 0;    //Index of the Mode
int modeRun = 0;    //Run Length of the current Mode

int currInd = 0;    //Index of Current Test
int currRun = 0;    //Current Run Length

int ind = 0;        //Working Index

//Count the run for the first number in the array and initialize the currInd
//I had this as an if inside the next while loop but it only executes for the first
//number so I just separated it so it wasn't a Kobayashi Maru, hence wasting processing.
while(numArr[ currInd ] == numArr[ modeInd ])
{
modeRun++;
currInd++;
}

//Iterate through every element.
while(ind < numFilled - 1)
{
//Test if the working num is part of the current run:
if(numArr[ ind ] == numArr[ currInd ])
{
currRun++;
}//end consecutivity test.
else
{
currInd = ind;
currRun = 0;
}//end non-consecutive branch.

//Test if the current run is longer than the recorded mode:
if(currRun > modeRun)
{
modeInd = currInd;
modeRun = currRun;

//Move the currInd to the NEXT working index.
currInd = ind + 1;
currRun = 0;
}//End if

ind++;
}//End while

return modeInd;
}//End CalcMode();
``````
-

If you have a sorted array and want to determine the most frequently-occurring value, use the fact that all repetitions of the same value will be adjacent.

Now you know what you're aiming for, can you write it yourself, or do you want to see the code?

Hint: you don't need an associative store of counters off to the side, only:

• the most-occurring value so far (longest run seen)
• the number of times it occurred (run length)
• the value in the current run
• the length of the current run so far
• a working index to iterate over the input array

It's a 1-pass algorithm with linear time and constant space overhead. It's actually related to run-length encoding, if that helps.

-
This is what I was originally planning on doing but I couldn't figure out a way to properly implement it. The program isn't due until tomorrow morning so I'll give it another try. Thanks! –  JDiPierro Sep 10 '12 at 12:10
Just finished implementing that algorithm. If I can, I'll edit the code into the question, if not it's here: pastebin.com/rsdm5txr –  JDiPierro Sep 10 '12 at 12:56

Try not to use the built-in array unless you have a constant sized data.

``````typedef int IntArr[MAX_ELEMENTS];
``````

What happens if you have more than MAX_ELEMENTS.
In C++ you would generally use a vector to hold this information.

`````` typedef std::vector<int> IntArr;
``````

Don't see any benifit in putting the filename in a variable like this:

``````const string FILENAME = "data.dat";
``````

Also it is traditional to reserve names that are all uppercase as MACROS. So you will confuse people that understand normal C++ into thinking these are macros names. So try and use camel case for you variable names (its also a lot nicer to read when code is not shooting at you).

Your loop for reading is correct. Which is a bit of a surprise as just testing the stream like that is usually an anti-pattern. But we can make that loop simpler:

``````    int num;
din >> num;

while(din)
{
numArr.push_back(num);  // remember I changed this to a vector

din >> num;
}
``````

First improvement: The result of the read operation (operator>>) is a stream (this allows chaining). But when a stream is used in a boolean context (like above) it is converted to a bool like value that can be testes. We can use and change the above loop to this:

``````    int num;
while(din >> num)
{                          // If the read worked we enter the loop body.
numArr.push_back(num);
}
``````

But using the C++ algorithm library we can reduce this one more time:

``````    std::copy(std::istream_iterator<int>(din),
std::istream_iterator<int>(),
std::back_inserter(numArr));
``````

Now you have a print specifically print an array in reverse order: We can use the algorithms to do that for you:

``````void Print(const IntArr& outArr, int numFilled);

// can be replaced with:

// Print the array in forward order
std::copy(numArr.begin(), numArr.end(), std::ostream_iterator<int>(std::cout, "\n"));

// Print the array in reverse order order
std::copy(numArr.rbegin(), numArr.rend(), std::ostream_iterator<int>(std::cout, "\n"));
``````

You can use the standard routines to sort the vector (or a normal array).

``````void Sort(IntArr& outArr, int numFilled);

// can be replaced with:

std::sort(numArr.begin(), numArr.end());
``````
-
Thanks for the answer. Unfortunately a lot of what you suggested is out of my control. The array is at the instruction of the professor. I asked last semester we're not allowed to use Vectors as far as I know, as they haven't covered them in class, plus having all those methods is the easy way out and they want us to do everything by hand for learning. Same thing goes for the capitals on the constants. Our class' documentation standards states that constants must be declared in all caps. –  JDiPierro Sep 7 '12 at 0:15
OK. I understand about the learning stuff and I agree with that. But you can tell you professor that I said he was an idiot. Using all caps for constants will cause problems as macro names have no scope boundaries and those names are common enough that it is inevitable that they will be used. –  Loki Astari Sep 7 '12 at 0:25
You can actually go even one more step in reading the data into the vector: initialize the vector from the iterators: `std::vector<int> numArray((std::istream_iterator<int>(din)), std::istream_iterator<int>());` (the seemingly redundant parens on the first argument prevent the most vexing parse). Since the sort seems to be used only to find the median, you can use `nth_element` instead. –  Jerry Coffin Sep 7 '12 at 6:09
@JerryCoffin: The reason I don't like that technique is for maintainability. Having to explain why you need an extra set of paren can be painful. Thus I prefer to use one extra iterator. –  Loki Astari Sep 7 '12 at 6:31
@JerryCoffin: I think using `::din` would be clearer than adding redundant parens. –  Anton Golov Sep 7 '12 at 7:34