Boyer-Moore's Voting Algorithm

Feroz Ahmad bio photo By Feroz Ahmad Comment
Moore's Voting algorithm has 2 parts : 1. First part of running Moore's Voting algorithm only gives you A candidate which occurs "most" of the time in the given array. 2. In the second part, we need to iterate over the array once again to determine if this candidate occurs maximum number of times (i.e. greater than size/2 times). First iteration is to find the candidate and second iteration is to check if this element occurs majority of times in the given array. So time complexity is: O(n) + O(n) ≈ O(n) 1.Finding a Candidate: The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. findCandidate(a[], size) 1. Initialize index and count of majority element maj_index = 0, count = 1 2. Loop for i = 1 to size – 1 (a)If count == 0 maj_index = i; count = 1 (b)If a[maj_index] == a[i] count++ (c)Else count--; 3. Return a[maj_index] -- 2. Check if the element obtained in step 1 is majority printMajority (a[], size) 1. Find the candidate for majority 2. If candidate is majority. i.e., appears more than n/2 times. Print the candidate 3. Else Print "NONE"
comments powered by Disqus