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
- 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.
where we also discuss the rather convoluted history of the algorithm's publication.
[Best Ideas]
[Publications]
[Research]
[Home]