Moore's Voting Algorithm

Jun 5, 2013 at 11:21pm
Hey guys I need help understanding how this code works for finding a majority element in an array. I understand the first main function, and also the bool function, but i do not understand the printmaj and the findmaj function. Could anyone throoughly explain how and why they work?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 int findmaj(int *, int);
bool majelement(int *, int, int);
void printmaj(int a[],int counter);

int main()
{

	int a[1000];
    int numofval,counter;
    do{
    cout<<"How many values to check?"<<endl <<endl;
    cin>>numofval; 
    cout<<"Enter values:"<<endl;
    for(counter=0;counter<numofval;counter++)
    {
    	cin>>a[counter];
    }
    printmaj(a, counter); 
    }
    while(numofval!=0);

    return 0;
}
bool majelement(int a[], int counter, int cand)
{
    int i, count = 0;
    for (i = 0; i < counter; i++)
       if(a[i] == cand)
         count++;
       if (count > counter/2)
         return 1;
       else
       return 0;

}
int findmaj(int a[], int counter)
{

	int maj_index = 0, count = 1;
    int i; 
    for(i = 1; i < counter; i++)
    {
        if(a[maj_index] == a[i])
            count++;
        else
            count--;
        if(count == 0)
        {
            maj_index = i;
            count = 1;
        }
    }
    return a[maj_index];
}
void printmaj(int a[], int counter)
{
  int cand = findmaj(a, counter);
  if(majelement(a, counter, cand))
    cout<<"The majority element is:" <<cand;
  else
    cout<<"There is no majority element";
}
Topic archived. No new replies allowed.