Thread: Mode of an array (with restricted command terms)

Hey all!
I am writing a code in C to find the mode of an array of numbers. I understand that this has been solved before but I am only allowed to use certain command terms in my program.
I am allowed to use loops, if and while statements, flags.
If I understand it correctly I need one loop that compares each term in the array to the other terms and stores how many times each number appears in each array.
So:
Input: A list of numbers (non integers too)
Output: the mode of the list of numbers. (If two numbers appear the same amount of times display no mode)

I already have the typing in of the numbers done, so I need the loop to check the array for how many times each number appears, store that in another array. Another loop to check the last array to see which number if the biggest and what it corresponds to.

Thank you so much!

Surely that cannot be the whole/correct task description. I assume that since you're asking the question that you're new to programming and based on that I conclude that either your instructor is insane (this is not a trivial exercise, especially since it involves "non-integers"), or that you've described the task required incorrectly.

Originally Posted by stahta01

I would create a second array that contains the value and number of times it existed in the list.

I wouldn't, unless you need the entire histogram of unique values.

If you do need the histogram, then using it does make a lot of sense, though. Just make each histogram bin represent an unique value, and mode is the bin with the highest count. You can do this in linear time, too.

If you want to find minimum, maximum, and median, it is easier to just sort the values first. Then, the first element in the array is the minimum, the last element in the array is the maximum, the middle element in the array is the median (which is very useful in e.g. benchmarking). You can find out the average=mean (by summing all the values and dividing by the count), and the mode, using a single linear pass over the array.

The logic for finding the mode in a sorted array is simple, and can be done in linear time. In pseudocode:

Code:

    best_multiple := false
    best_value := array[0]
    best_count := 1

    if length < 2
        return best_value (only value in the array)

    curr_value := best_value
    curr_count := best_count

    for index := 1 .. length-1

        if array[index] == curr_value
            curr_count = curr_count + 1
        else
            if curr_count > best_count
                best_value = curr_value
                best_count = curr_count
                best_multiple = false
            else
            if curr_count == best_count
                best_multiple = true

            curr_value = array[index]
            curr_count = 1

    if curr_count > best_count
        best_value = curr_value
        best_count = curr_count
    else
    if curr_count = best_count
        best_multiple = true

    if best_multiple
        return nothing (more than one mode)
    else
        return best_value (occurs best_count times)

Without sorting the array, you do need a double loop to find the mode. In pseudocode:

Code:

    if length < 1
        return nothing (empty array)
    if length < 2
        return array[0] (only one item in the array)
    if length < 3
        return nothing (two values in array, both modes)

    best_multiple = false
    best_value = 0
    best_count = 0

    for i = 0 .. length-1
        count = 0

        value = array[i]

        for k = 0 .. length-1
            if array[k] == value
                count = count + 1

        if count > best_count
            best_count = count
            best_value = array[i]
            best_multiple = false
        else
        if count == best_count
            best_multiple = true

    if best_multiple == true
        return nothing (because multiple modes)
    else
        return best_value (which occurs best_count times)

In the latter case, it is easy to either limit comparison to specific number of decimal digits (by multiplying with a suitable power of ten, then rounding, before comparison), or to consider all numbers that differ from the central value by at most epsilon as equal to value.

To limit to specific number of digits, use value = round(poweroften * array[i]) and if (value == round(poweroften * array[k])) , where poweroften is a suitable power of ten; 10¹=10 if you want one decimal digit, 10²=100 if two, 10³=1000 if three, and so on. (You can use pow(10, digits) from <math.h> to calculate poweroften.)

To look for values that differ by not more than epsilon, use value = array[i] as in the original two-nested-loops pseudocode above, but test using if (value - epsilon <= array[k] && array[k] <= value + epsilon).
This is basically a search for the largest group of similar values, where we try to find the value in the array that has the most neighbours within distance epsilon.
If for example the values in the array are known to have ±epsilon of random noise, this too is mode. This is really, really useful if the values are real-world measurements, and you need their mode!
Note that even if the data is sorted, a double loop is needed in this case.

I hope you don't mind me butting in, stahta01.

In general, I too recommend the histogram approach, because a histogram tells one much more about a distribution than just minimum, maximum, median, and mode. It's just that to calculate those four values, you don't need it, really. And for finding the mode in noisy data, the histogram approach does not really work (because the bin boundaries are exact).

To the OP: I deliberately provided you with much, much more information than you actually need. This, to me, serves two purposes: First, it shows others looking at problems involving finding the mode some real-world useful options. Second, while the post contains basically all information to solve the problem statement outlined in the first post, it is not copy-pastable: you need to read and think until you understand and can apply that understanding -- learn -- to make use of it. I consider this a win-win-I'mTooVerbose situation.

Originally Posted by stahta01

Does NOT bother me at all.

Good! I was butting in, and even if I disagreed, you did have good points in your post.

Originally Posted by stahta01

I was just guessing OP does not know how to sort

Quite, but I didn't want to just provide the nested-loop-no-sorting solution as pseudocode alone.

Massaging data is an interesting topic, and I wanted to make sure those trying to find the mode of some data see there are many ways to do it, and perhaps other, better ways to look at and characterize the data they have. You know, "lit the fuse", so to speak, even if nothing sticks for now.