A Linear Time Majority Vote Algorithm

This algorithm, which Bob Boyer and I invented in 1980 decides which element of a sequence is in the majority, provided there is such an element. How would you determine the majority element of:
sequence:  A A A C C B B C C C B C C
You could count the number of occurrences of each element. Here is how we do it, in one pass.

For details, see

where we also discuss the rather convoluted history of the algorithm's publication.

[Best Ideas] [Publications] [Research] [Home]