MJRTY - A Fast Majority Vote Algorithm isn't work [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Software Engineering Stack Exchange.

Closed 5 years ago.

Improve this question

The MJRTY algorithm sets out to solve the problem of finding the majority element in a stream (an element comprising more than 50% of the stream). Moore proposed to solve this by using only 2 pieces of information and a single scan of the data. Imagine you have a stream of names (“matt”, “timon”, “matt”, “matt”, “rob”, “ben”, …) and you wanted to know if any name appeared in more than half the stream. Boyer and Moore proposed the following:

count = 0
majority = ""

for val in stream:
    if count == 0:
        majority = val
        count = 1
    elif val == majority:
        count += 1
    else:
        count -= 1
print majority if count > 0 else "no majority!"

if stream = A A A A B B B B C => result = C, but it isn't truth.

step by step

step    val majority    count
0   A   A   1
1   A   A   2
2   A   A   3
3   A   A   4
4   B   A   3
5   B   A   2
6   B   A   1
7   B   A   0
8   C   C   1

About this algotithm: http://www.cs.utexas.edu/~moore/best-ideas/mjrty/

Answer 1

The Boyle-Moore algorithm only works if there is a majority, indeed. It is useful if you can assume that there is a majority, for instance when processing binary strings composed of 0 or 1: if the length of the string is odd, then you must have a majority.

The sequence A A A A B B B B C has 9 elements, so you need at least 5 occurences of an element to have a majority, and you don't have it. The result is therefore not significant.

Answer 2

Input          count          majority
A                1              A
A                2              A
A                3              A 
A                4              A
B                3              A
B                2              A
B                1              A
B                0              A
C                1              C

Count is not greater than 0. "no majority!"