Find the modal value of a sample of numbers

Question

I am currently interested in implementing statistical measures. Other measures like mean, variance, and covariance are easy, but the mode feels harder than I thought. Is this good enough?

Note: float is used because I don't really intend to use it on big enough numbers. The size can be changed if needed.

Note 2: We cannot use vectors, any statistical related functions, and any other tool that can impact the performance of the code. What we can use though, are basic data types (int, float, double, bool, char, and the long, short, and unsigned versions) and simple conditional and looping structures. To add, the auto keyword is not allowed.

Probably unrelated, but still relevant: Why did I use "we" instead of "I" in the second note?
I'm still learning C++ in school, so I am limiting myself to what we can do in school even though it can really improve the performance.

#include <iostream>

using std::cout;
using std::cin;

int main () {
    int N, uniques = 0, j = 0;
    // N: number of elements; uniques: unique elements in list; j: list index
    cin >> N;

    float list[N], counters[N][2];
    // list[N]: the list of elements
    // counters[N][2]: the list of unique elements and the number of appearances
    bool found = false;

    for (int i = 0; i < N; i++) {
        cin >> list[i];
        found = false;

        for (j = 0; j < uniques; j++) {
            if (counters[j][0] == list[i]) {
                counters[j][1]++;
                found = true;
                break;
            }
        }
        if (!found) {
            counters[uniques][0] = list[i];
            counters[uniques][1] = 1;
            uniques++;
        }
    }
    int max = counters[0][1], ind = 0, reps = 0;

    for (int k = 0; k < uniques; k++) {
        if (max == counters[k][1]) {
            reps++;
        } else if (max < counters[k][1]) {
            ind = k, max = counters[k][1];
            reps = 1;
        }
    }

    if (reps == 1) {
        cout << "The mode of the data set is " << counters[ind][0] << " appearing " << max << " times";
    } else {
        cout << "undetermined " << reps;
    }
    return 0;
}

---

I added comments about the variable names.

Answer 1

Here are some ideas to help you improve your code, and perhaps inspire you to learn more.

Reconsider using

The code currently contains these two lines:

using std::cout;
using std::cin;

That's not too terrible, but there are at least two ways to make it better. First would be to put those inside main to limit any possible conflicts there instead of globally. Better, in my view, would be to simply omit them and use std::cin and std::cout since they're only used in three lines in your entire program. That way readers will instantly see that you're using the std:: versions and not some other version.

Decompose your program into functions

All of the logic here is in main in one dense chunk of code. It would be better to decompose this into a separate function or functions.

Avoid non-standard features

Others have mentioned this, but declaring an array with anything other than a compile-time number is not in standard C++ and so that should be avoided. I hope your teacher isn't writing C++ code like this!

Use modern C++ features

It is very likely you haven't learned about std::ranges or various other algorithms and data structures yet, but just to whet your appetite, here's a rewrite of your program using C++20 and all of the tools in the toolbox:

#include <iostream>
#include <map>
#include <ranges>
#include <algorithm>

int main () {
    using myDataType = float;
    using myMapType = std::map<myDataType, unsigned>;
    myDataType value;
    myMapType counts;
    int N;
    for (std::cin >> N; N && std::cin >> value; --N) {
        ++counts[value];
    }
    auto mode = std::ranges::max_element(counts,{},&myMapType::value_type::second);

    std::cout << "The mode of the data set is " << mode->first 
              << " appearing " << mode->second << " times\n";
}

Use a more efficient algorithm

It's good to learn how to write your own code, but given your restrictions, your options are somewhat limited. Here's a suggestion for an alternative implementation that is somewhat more efficient, expressed in psuedo-code:

1. create "big enough" arrays for data and count
2. initialize overall item count and max element index to 0
3. for each read value:
   1. linearly search the data array for a matching value
   2. if it's new, add it to the array and set the count to 1 and increment the overall unique item count
   3. otherwise, it's not new so increment the count and compare to current max element index (updating the latter as appropriate)

At the end of this, the max element index will point to the index of the mode value and its associated count.

Answer 2

Leaving alone the run-time sized arrays, lets look at complexity.

The nested loops are wasteful, both timewise, and spacewise. Consider to

1. read all numbers,
2. sort them, and
3. count (now adjacent) equals to find the mode

This will reduce the time complexity from \$O(n^2)\$ to \$O(n)\$, and the space complexity from \$O(n)\$ to \$O(1)\$ (the counters array is not needed anymore).

Also, if each phase is implemented as a function, the code will be much cleaner, readable and testable.

PS: Even if you are not allowed to use std::sort, nobody forbids you to implement an efficient sorting algorithm.

Answer 3

This is not standard C++:

     int N;
     ⋮
     float list[N], counters[N][2];

Array dimensions are required to be compile-time constants. Prefer to use a dynamically-sized container such as std::vector.

Given the crazy constraints you're working under (effectively using only the C-compatible subset of C++ - I'll even assume that smart pointers are forbidden), you'll have to write

float *list = new float[N];

Don't forget to delete[] the storage when it's no longer required.

Answer 4

Considering the restrictions, the algorithm looks nice to me, but the code itself is a bit casual. I post mine for you to compare the code structures.

void findMode()
{        
    const int maxSampleSize = 100000;
    int sampleSize;
    std::cin >> sampleSize;    
    if (sampleSize <= 0 || sampleSize > maxSampleSize) {
        std::cerr << "Invalid sample size";
        return;
    }

    static float uniqueValues[maxSampleSize];
    static int frequencies[maxSampleSize];
    int uniqueSize = 0;
    for (; sampleSize > 0; --sampleSize) {
        float value;
        std::cin >> value;
        int i = 0;
        while (i < uniqueSize && uniqueValues[i] != value)
            ++i;
        if (i == uniqueSize) {
            frequencies[uniqueSize] = 1;
            uniqueValues[uniqueSize] = value;
            ++uniqueSize;
        }
        else
            ++frequencies[i];
    }

    int modePos = 0;
    int modes = 1;
    for (int i = 1; i < uniqueSize; ++i) {
        if (frequencies[i] == frequencies[modePos])
            ++modes;
        else if (frequencies[i] > frequencies[modePos]) {
            modePos = i;
            modes = 1;
        }
    }

    if (modes == 1) {
        std::cout << "The mode of the data set is " <<
            uniqueValues[modePos] << " appearing " <<
            frequencies[modePos] << " times";
    }
    else
        std::cout << "undetermined " << modes;
}

I use static array variables because array sizes are large. Otherwise, we would eventually run into troubles on Windows if arrays would be allocated on stack.

Although, the example is not a model. It is common for scientists, like in your case, to write a use-once code which doesn't require further maintanance.

---

We can observe that in the worst case (when all values are different) we perform about N * N "elementary" operations on the array elements. To improve performance, we could sort arrays first (e.g., with heapsort in about N * log(N) operations in the worst case), and then find mode in a single run over sorted elements. Here, I use insertion sort for simplicity. It performs in about N * N operations.

void insertionSort(float arr[], int n)
{
    for (int i = 1; i < n; ++i) {
        int x = arr[i];
        int j = i - 1;
        for (; j >= 0 && arr[j] > x; --j)
            arr[j + 1] = arr[j];
        arr[j + 1] = x;
    }
}

void findMode()
{
    int sampleSize;
    std::cin >> sampleSize;

    const int maxSampleSize = 100000;
    if (sampleSize <= 0 || sampleSize > maxSampleSize) {
        std::cerr << "Invalid sample size";
        return;
    }

    static float sample[maxSampleSize];
    for (int i = 0; i < sampleSize; ++i)
        std::cin >> sample[i];
    
    insertionSort(sample, sampleSize);

    int modes = 0;
    int modePos = 0;
    int maxCount = 0;
    for (int i = 1, count = 1; i <= sampleSize; ++i) {
        if (i < sampleSize && sample[i - 1] == sample[i])
            ++count;
        else {
            if (count == maxCount)
                ++modes;
            else if (count > maxCount) {
                maxCount = count;
                modePos = i - 1;
                modes = 1;
            }
            count = 1;
        }
    }

    if (modes == 1) {
        std::cout << "The mode of the data set is " <<
            sample[modePos] << " appearing " <<
            maxCount << " times";
    }
    else
        std::cout << "undetermined " << modes;
}