Boyer–Moore majority vote algorithm in C

Boyer-Moore majority vote algorithm

Boyer–Moore majority vote algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements of the array, that have more than N/ 2 occurrences. Boyer–Moore majority vote algorithm works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

Boyer-Moore majority vote algorithm in C

Algorithm :

  • Take the size of array and store it in variable n.
  • Take n elements of the array from the user.
  • Declare two variable one is maj_index and initialize it with 0, and one variable count with value 0.
  • Run a loop from index 1 to n-1
  • Check if a[i]==a[maj_index] then increase the value of count by 1, else decrease it by 1.
  • If count becpmes zero then set maj_index=i and count =1.
  • Now create one function check that will check whether maj_index value presents n/2 times or not.
  • If it is present then return 1, otherwise 0(means no elements presents more than n/2 times).

C code based on above algorithm

#include <stdio.h>

int find_majority( int a[], int size)
{
int maj_index=0;

int count=1;

for(int i=1; i<size; i++){

if(a[i]==a[maj_index])
count++;

else
count--;

if(count==0)
{
maj_index=i;
count=1;

}

}

return a[maj_index];
}

int check_maj(int a[], int n , int k)
{
int count=0;

for(int i=0;i<n;i++){

if(a[i]==k)
count++;

}
if(count>n/2)
return 1;

else
return 0;

}

int main(){

int k,n;

scanf("%d", &n);

int a[n];

for(int i=0; i<n; i++)
scanf("%d", &a[i]);


k= find_majority( a,n);

if(check_maj(a,n,k))
printf("Majority element : %d", k);

else
printf("No Majority element\n");

return 0;
}
Output

6

1 2 5 2 2 2

Majority element : 2