Finding Mode of a Unsorted array.

[JainishP]

I was just wondering how I would go about finding a mode of a unsorted array. I know that if it's sorted I can pass data into a 2 dimensional array and find the largest count.

I tried to write some code counting the first value, but it ends up giving me the wrong answer.

int getMode(int test[], int SIZE)
	{
	int currvalue = test[0];
	int count = 1;
	int countmax = 1;
	int mode = test[0];


	for (int i = 0; i < SIZE; ++i)
		{
		if (test[i] == currvalue)
			++count;
		else
			{
			if (count >= countmax)
				{ 
				countmax = count;
				mode = test[i];
				}
			currvalue = test[i];
			count = 2;
			}
		}
	return mode;
	}

[siddhant3s]

You could create a array called count and store the number of occurrence of each of the element of test[] in that. Then simply find the largest element of count[].
Suppose then the largest element of count[] is the k-th element, then the mode will be test[k].

[JainishP]

You could create a array called count and store the number of occurrence of each of the element of test[] in that. Then simply find the largest element of count[].
Suppose then the largest element of count[] is the k-th element, then the mode will be test[k].

How would I make it so that it counts a value again if it shows up in the array again?

[siddhant3s]

>>How would I make it so that it counts a value again if it shows up in the array again?
Good question.
The best thing would to use a std::map if you are comfortable using the standard library.

Otherwise, things could get very unhealthy.
Here is what to do other wise if you don't want to use STL:
Run through the test[].
For every i-th element Run through the rest of the array( using a nested loop) and then check if that value repeats ( if yes, find out how many times)
Store the repetition in the count[]

I still strongly suggest you to use std::map.

[Ancient Dragon]

The program needs some way to keep track of the values and the number of times the values appear in the array. Then its a simple matter to find the value that appears the largest number of times

struct item
{
    int value;
    int count;
};

now build an array of the above structures and use it to keep track of how many times each number appears in the array passed to that function.

[edit]I didn't see the above two posts -- was busy working this problem out :) I would agree that map would be better than above, but that would depend on the OPs level of experience, and whether he is allowed to use std::map in his program. [/edit]

[JainishP]

The program needs some way to keep track of the values and the number of times the values appear in the array. Then its a simple matter to find the value that appears the largest number of times

struct item
{
    int value;
    int count;
};

now build an array of the above structures and use it to keep track of how many times each number appears in the array passed to that function.

[edit]I didn't see the above two posts -- was busy working this problem out :) I would agree that map would be better than above, but that would depend on the OPs level of experience, and whether he is allowed to use std::map in his program. [/edit]

Not very experienced with C++, and am not sure I want to use std::map as that's something we haven't learned yet, so it would be weird using that in a solution.

[Ancient Dragon]

have you been taught structures yet? If not, you could do the same thing with two simple int arrays, one to hold the values and another to hold counts.

[JainishP]

have you been taught structures yet? If not, you could do the same thing with two simple int arrays, one to hold the values and another to hold counts.

No nothing about structures yet.

[Ancient Dragon]

Ok, then just create two int arrays. The first array should hold the value and the second the number of times that value appears in the test[] array, which is the parameter to the function.

For each value in test[] your program will first search the values[] array to see if the it is already in that array. There are two possibilities:

• The value in test[] does not exist in values[]. Add the value in test[] to the next available slot in values[] and set the quantity in the corresponding row of counts[] to 1.
• The value in test[] already exists in values[]. In this case just simply increment the corresponding row of counts[] by 1.

[ArkM]

I think no need in additional storage and other complicated stuff. A brutal force solution has complexity O(n*n):

template <typename T> // O(n*n)
int modeIndex(const T* a, int n)
{ // Returns the 1st mode candidate index or -1 if no values.
    int midx = -1;
    if (a && n > 0) { // parms check-out
        midx = 0;
        int nidx, ncnt, mcnt = 1;
        for (int j, i = 0; i < n; ++i) {
            nidx = i; // the next mode candidate
            ncnt = 1;
            if ((j = i + 1) < n && a[j] != a[midx]) { // opt
                const T& amod = a[nidx]; // yet another opt
                do {
                    if (a[j++] == amod)
                        ++ncnt;
                } while (j < n);
                if (mcnt < ncnt) {
                    //cout << "new ";
                    midx = nidx;
                    mcnt = ncnt; // keep the 1st candidate
                }
            }
            //cout << "mode " << a[midx] << "(" << ncnt << ")\n"; 
        }
    }
    return midx;
}

Probably a pointer-based solution is the best (the fastest) choice. Try to implement it.

[Ancient Dragon]

ArkM is right in that you don't need additional arrays. But the code he posted is way beyond what you have studied so far. You can do the program with two simple loops, which count the number of times each value appears in the array. Then just keep track of which value appears the largest number of times.

[ArkM]

ArkM is right in that you don't need additional arrays. But the code he posted is way beyond what you have studied so far. You can do the program with two simple loops, which count the number of times each value appears in the array. Then just keep track of which value appears the largest number of times.

Yes, I agree. I understand that the code "is way beyond" but the core loops are not depended on templates and other decorations so I hope it helps...