File Exchange

image thumbnail

Boyer–Moore majority vote algorithm

version 1.0.0.0 (1.45 KB) by Reza Ahmadzadeh
Boyer–Moore majority vote algorithm

2 Downloads

Updated 09 Dec 2015

View License

%% Boyer–Moore majority vote algorithm
% The Boyer-Moore Vote Algorithm solves the majority vote problem in
% linear time O(n) and logarithmic space O(\log n). The majority vote
% problem is to determine in any given sequence of choices whether
% there is a choice with more occurrences than all the others, and if so,
% to determine this choice. Mathematically, given a finite sequence
% (length n) of numbers, the object is to find the majority number
% defined as the number that appears more than floor(n/2) times.%
%
% Example:
%
% consider we want to find the majority element in 'aaaccbbcccbcc'
% MajorityVote('aaaccbbcccbcc')
% ans =
% c
%

Cite As

Reza Ahmadzadeh (2020). Boyer–Moore majority vote algorithm (https://www.mathworks.com/matlabcentral/fileexchange/54394-boyer-moore-majority-vote-algorithm), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (2)

Reza Ahmadzadeh

Hi Kwame,
For an element to be considered as majority, there is a condition that says: the number of occurrence for that element has to be bigger than half of the number of elements in the sequence. In the example MajorityVote('12323234232') the element 2 has been occurred 5 times, but 5<floor(11/2) is not satisfied, so there is no majority. The answer is the same for your next example MajorityVote('3344555') where the element 5 has been repeated 3 times and floor(7/2)=3 and since 3>3 is not valid there is no majority.

Hello Reza, I tried your code using MajorityVote('12323234232') and the answer was "There is no Majority" while in fact, the answer is 2. I also tried MajorityVote('3344555') and instead of the answer being 5, it again gave me "There is no Majority". However, MajorityVote('AAAAAAAACCCCBBB') = A which is correct. Also, MajorityVote('12222') = 2 which is correct. Is the code behaving as you would expect? thanks

MATLAB Release Compatibility
Created with R2007a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!