Skip to main content
gamedev.net
🔒 Locked

Finding the Mode Program

Started by Noegddgeon Sep 13, 2010 at 8:05 PM 8 replies 800+ views
Original Post
Noegddgeon
Noegddgeon
Hey, everybody. I am attempting to write a program as an exercise to find the mode of a set of data. I am having a little bit of trouble constructing it, so I would like to post my code in the hopes of someone being able to tell me what I am doing wrong :] Thank you all in advance, I really appreciate your help.

#include <iostream>using namespace std;int findMode(int[], int);int main(){    int arrOrig[30];        cout << "30 Pie Values Will Be Entered\n";    for (int i = 0; i < 30; i++)    {        cout << "Please enter Value " << i+1 << ": ";        cin >> arrOrig;    }        cout << "The mode is " << findMode(arrOrig, 30) << endl;        return 0;}int findMode(int *original, int num){    int *valArray = new int[num];    int *quantArray = new int[num];    int mode;        int valCounter = 0;        for (int i = 0; i < num; i++)       // Check each value in array    {        if (i == 0)                     // First value        {            valArray = original;            quantArray++;            valCounter++;            continue;        }        for (int j = i; j < num; j++)               // For each element        {            for (int k = 0; k < valCounter; k++)    // Check already tracked            {                if (original[j] == valArray[k])     // If already checked                {                    quantArray[k]++;                // Increment                    break;                }                else                {                    valArray[valCounter] = original[j];     // Add val                    valCounter++;                }            }        }    }        mode = quantArray[0];        for (int m = 0; m < valCounter; m++)    {        if (quantArray[m] > mode)        {            mode = valArray[m];        }    }        return mode;}


My approach was to have three arrays:

1. original: Stores the 30 data entries originally inputed.
2. valArray: Stores the unique entries in the original array.
3. quantArray: Parallel array to valArray that stores the number of times that particular corresponding value in valArray exists in the original array.

It seems a little bit convoluted, but I have been given no clear guidance or algorithm to complete this.... it is to me a new and original approach. Thank you all in advance again :]
alvaro
alvaro
The obvious algorithm for this uses a std::unordered_map to count how many times each number has appeared. It's fast and -thanks to the STL- simple.
Noegddgeon
Noegddgeon
Quote:
Original post by alvaro
The obvious algorithm for this uses a std::unordered_map to count how many times each number has appeared. It's fast and -thanks to the STL- simple.


Thank you for your reply, alvaro. However, I can't use the standard library yet... at least not that bit of it. The chapter is focused on arrays and pointers mostly, so if there's a way I can do it using those tools instead, it would be much better. Sorry I didn't clarify that in the beginning :p But thank you for the suggestion; if I were that far in the book, I'd certainly try to implement it.
Sneftel
Sneftel
Sorting is your friend here. After the array is sorted, all equal values will end up right next to each other. This is a useful place for them to be.
Noegddgeon
Noegddgeon
Quote:
Original post by Sneftel
Sorting is your friend here. After the array is sorted, all equal values will end up right next to each other. This is a useful place for them to be.


Thank you very much for your suggestion, Sneftel. That actually sheds a lot of light on the situation.... I have a new approach in mind now. I'll work on implementing it and then re-post as soon as it's finished. :]
Noegddgeon
Noegddgeon
Okay, I've tried re-implementing it using a sorting approach and then an algorithm that just goes through and calculates which number occurs the most. Here's the source code:

#include <iostream>using namespace std;int findMode(int[], int);int main(){    int arrOrig[30];        cout << "30 Pie Values Will Be Entered\n";    for (int i = 0; i < 30; i++)    {        cout << "Please enter Value " << i+1 << ": ";        cin >> arrOrig;    }        cout << "The mode is " << findMode(arrOrig, 30) << endl;        return 0;}int findMode(int *original, int num){    int *uniqueArray = new int[num];    int temp = 0;    int unique;    int modeCounter = 0;    int mode;        int takeIndex, smallest;        cout << "Sorting loop started.\n";        for (int i = 0; i < num; i++)    {        smallest = original;        for (int j = i; j < num; j++)        {            if (original[j] < smallest)            {                takeIndex = j;                smallest = original[j];            }        }        swap(original[takeIndex], original);    }        for (int l = 0; l < num; l++)    {        int counter = 0;        cout << original[l] << " ";        if (counter % 5 == 0)        {            cout << endl;        }    }        cout << "Sorting loop ended.\n";        unique = original[0];        cout << "Mode loop started.\n";        for (int k = 0; k < num; k++)    {        if (original[k] == unique)        {            modeCounter++;        }        else        {            if (modeCounter > temp)            {                temp = modeCounter;                modeCounter = 0;                mode = unique;                unique = original[k];            }            else            {                modeCounter = 0;                unique = original[k];            }        }    }        cout << "Mode loop ended.\n";        return mode;}


However, I find that sometimes the output will be correct, while at other times it will be wrong. Sometimes it sorts properly, while other times it does not, and I fear this may be the root of the problem. I greatly appreciate all help and guidance :]
fastcall22
fastcall22 
#include <iostream>using namespace std;void printarr( int* arr, int num ) {	for ( int i = 0; i < num-1; ++i )		cout << arr << ' ';	cout << arr[num-1] << endl;}void gdSort( int* arr, int num ) {	int smallest;	int takeIndex;	printarr( arr, num );	for (int i = 0; i < num; i++)	{		smallest = arr;		for (int j = i; j < num; j++)		{			if (arr[j] < smallest)			{				takeIndex = j;				smallest = arr[j];			}		}		swap(arr[takeIndex], arr);		printarr( arr, num );	}}int main() {	int arr[] = { 6, 4, 3, 9, 7, 2, 5, 4, 1 };	gdSort( arr, sizeof(arr)/sizeof(arr[0]) );}

6 4 3 9 7 2 5 4 11 4 3 9 7 2 5 4 61 2 3 9 7 4 5 4 61 2 4 9 7 3 5 4 61 2 4 3 7 9 5 4 61 2 4 3 4 9 5 7 61 2 4 3 4 5 9 7 61 2 4 3 4 5 6 7 91 2 4 3 4 5 6 9 71 2 4 3 4 5 6 9 7

HINT:
It seems the sorting method seems to swap, even if "smallest" and "takeIndex" wasn't found in the inner loop.
Noegddgeon
Noegddgeon
Thank you very much for the reply, but I can't exactly discern what it is I've done wrong based on what you wrote without any comments or information. :[
fastcall22
fastcall22
Quote:
Original post by Noegddgeon
Thank you very much for the reply, but I can't exactly discern what it is I've done wrong based on what you wrote without any comments or information. :[


Sorry, I have a terrible habit of repeatedly editing a post after posting it. Anyways, you're just missing one piece of the puzzle: At the current state of your code, the sorting algorithm will perform a swap, even if there wasn't an element after i that is lower than arr. The code sample in my previous post demonstrates it, as the eighth iteration is the correct sorted array, however, becomes unsorted in the next two iterations.
Noegddgeon
Noegddgeon
Ahhhh, thank you so much :] I fixed the problem. I'll post the finished code here:

#include <iostream>using namespace std;int findMode(int[], int);int main(){    int arrOrig[30];        cout << "30 Pie Values Will Be Entered\n";    for (int i = 0; i < 30; i++)    {        cout << "Please enter Value " << i+1 << ": ";        cin >> arrOrig;    }        cout << "The mode is " << findMode(arrOrig, 30) << endl;        return 0;}int findMode(int *original, int num){    int *uniqueArray = new int[num];    int temp = 0;    int unique;    int modeCounter = 0;    int mode;        int takeIndex, smallest;        cout << "Sorting loop started.\n";        for (int i = 0; i < num; i++)    {        smallest = original;        bool swapp = false;        for (int j = i; j < num; j++)        {            if (original[j] < smallest)            {                takeIndex = j;                smallest = original[j];                swapp = true;            }        }        if (swapp)        {           swap(original[takeIndex], original);           takeIndex = original[i+1];        }    }        for (int l = 0; l < num; l++)    {        int counter = 1;        cout << original[l] << " ";        counter++;        if (counter % 5 == 0)        {            cout << endl;        }    }        cout << "Sorting loop ended.\n";        unique = original[0];        cout << "Mode loop started.\n";        for (int k = 0; k < num; k++)    {        if (original[k] == unique)        {            modeCounter++;        }        else        {            if (modeCounter > temp)            {                temp = modeCounter;                modeCounter = 0;                mode = unique;                unique = original[k];            }            else            {                modeCounter = 0;                unique = original[k];            }        }    }        cout << "Mode loop ended.\n";        return mode;}


Could be faster probably, more efficient, or at least cleaner, but it finally works. Thank you very much for your help :]

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.