Boyer–Moore majority vote algorithm.

Boyer-Moore voting use case.


In Computer science the Boyer-Moore voting algorithm is a famous optimal algorithms which is used for finding the majority element among the given elements list that have more than N/ 2 occurrences. This algorithm uses the logic that if an element occurs more than N/2 times, the remaining elements other than this would certainly be less than half of the list. The name of the algorithm comes after it's inventors Robert S. Boyer and J Strother Moore, who published it in 1981.

Boyer–Moore majority vote algorithm.



The process logic is simple:

- Сhoose a candidate from the given set of elements.
- Iterate from input elements, if the element is equal to candidate element, increase the votes.
- Otherwise, decrease the votes.
- If votes become 0, choose a new candidate.


Boyer–Moore majority vote algorithm Python code:



def findMajority(arr, n):
    candidate = -1
    votes = 0
     
    # Finding majority candidate
    for i in range (n):
        if (votes == 0):
            candidate = arr[i]
            votes = 1
        else:
            if (arr[i] == candidate):
                votes += 1
            else:
                votes -= 1
    count = 0
     
    # Checking if majority candidate occurs more than n/2 times
    for i in range (n):
        if (arr[i] == candidate):
            count += 1
             
    if (count > n // 2):
        return candidate
    else:
        return -1
 
# Driver Code
arr = [ 2, 2, 2, 4, 2, 11, 3, 5, 2, 7, 2 ]
n = len(arr)

majority = findMajority(arr, n)
print(" The majority element is :" ,majority)

OUT: The majority element is : 2





See also related topics: