Boyer and Moore's Linear Time Voting Algorithm

This is a simple linear time voting algorithm designed by Robert S Boyer and J Stother Moore in 1980 which is discussed in their paper MJRTY - A Fast Majority Vote Algorithm.

This algorithm decides which element of a sequence is in the majority, provided there is such an element. 

Suppose there are n characters (objects/candidates). When the ith element is visited, the set can be divided into two groups,ca group of k elements in favor of current selected candidate and a group of elements that disagree.After processing all, we can conclude that candidate selected can be considered majority if there's any !

When the pointer forward over an element e:

If the counter is 0, we set the current candidate to e and we set the counter to 1.
If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
When we are done, the current candidate is the majority element, if there is a majority.

I have written a simple java implementation.




Sometime ties may occur. But this algorithm doesn't fit as the solution.For an assurance, if the vote is greater than n/2, the candidate which is returned as majority it is announced to be the selected one. This counting phase can be done when the increment for the candidate happens.This algorithm is really effective when the data is read from a tape.The algorithm only works when at least half of the elements constitute the majority.

Reference
http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/example.html