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

Question

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();

Answer 1

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.

Answer 2

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());