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.
- MJRTY - A Fast Majority Vote Algorithm, with
R.S. Boyer. In R.S. Boyer (ed.), Automated Reasoning: Essays in Honor
of Woody Bledsoe, Automated Reasoning Series, Kluwer Academic Publishers,
Dordrecht, The Netherlands, 1991, pp. 105-117.