A Linear-time Majority Vote Algorithm

Today I was looking for fast string-searching algorithms. Along the way I stumbled upon Moore's (one of the creators of Boyer-Moore string search) homepage which has a collection of other interesting algorithms, among others the one from the title.

Problem: How to decide, in one pass which element of a sequence is in the majority, provided there is such an element. This page has a nice animation. The following is a quotation of the algorithm from the page:

As we sweep through the sequence, we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0. When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate. When we are done, the current candidate is the majority element, if there is a majority.

If you must confirm that the chosen element is indeed the majority element, you must take one more linear pass through the data to do it.

Links: writings

Last edited Sun Apr 6 11:06:34 2008
This work is licensed under a Creative Commons Attribution-No Derivative Works 3.0 License.