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.

	package test.algorithm;
	/**
	* A stupid tester for the Boyer and Moore's Linear Time Voting Algorithm
	*
	* The algorithm only works when at least half of the elements constitute the majority.
	*
	* @author harisgx
	*
	*/
	public class TestMajorityVotingAlgorithm {
	/**
	* @param args
	*/
	public static void main(String[] args) {
	Object [] data = {'A', 'A', 'A', 'C', 'C', 'B', 'B', 'C', 'C', 'C', 'B', 'C', 'C'};
	TestMajorityVotingAlgorithm tm = new TestMajorityVotingAlgorithm();
	Majority majority = tm.findMajority(data);
	System.out.println(majority.getCandidate().getValue());
	System.out.println(majority.leading());
	}
	public Majority findMajority(Object[] data){
	Majority majority = new Majority();
	for(Object obj : data){
	//If the counter is 0, we set the current candidate to e and we set the counter to 1.
	if(majority.leading() == 0){
	majority.setCandidate(new Candidate(obj));
	}else{
	//If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.
	if(majority.getCandidate().equals(obj)){
	majority.increment();
	}else{
	majority.deccrement();
	}
	}
	}
	return majority;
	}
	public static class Majority {
	private Candidate candidate;
	private int leading;
	public Majority(){
	}
	public Candidate getCandidate() {
	return candidate;
	}
	public void setCandidate(Candidate cand) {
	this.candidate = cand;
	leading = 1;
	}
	public int leading() {
	return leading;
	}
	public void increment(){
	leading ++;
	}
	public void deccrement(){
	leading --;
	}
	}
	public static class Candidate {
	private Object obj;
	public Candidate(Object obj){
	this.obj = obj;
	}
	public Object getValue(){
	return this.obj;
	}
	@Override
	public boolean equals(Object obj) {
	return this.obj.equals(obj);
	}
	}
	}

view raw TestMajorityVotingAlgorithm.java hosted with ❤ by GitHub

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