Empower Your Python Projects with 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.
Boyer–Moore majority vote meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.




    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.


  1. Boyer–Moore majority vote algorithm Python code:


  2. 
    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)
    

  3. Boyer–Moore algorithm Python code result:


  4. OUT: The majority element is : 2





See also related topics: