majority

Boyer-Moore Majority Vote Algorithm

https://github.com/niswegmann/majority

Latest on Hackage:1.1

This package is not currently in any snapshots. If you're interested in using it, we recommend adding it to Stackage Nightly. Doing so will make builds more reliable, and allow stackage.org to host generated Haddocks.

LicenseRef-PublicDomain licensed by Nis N. Wegmann
Maintained by [email protected]

The Boyer-Moore Majority Vote Algorithm determines if there in a list of votes is a candidate that holds more than half of the majority, and if so, finds this candidate. It does so in time linear in the length of the input list and constant memory. For a detailed description of the algorithm, see these papers:

  • Wim H. Hesselink, "The Boyer-Moore Majority Vote Algorithm", 2005;

  • Robert S. Boyer and J. Strother Moore, "MJRTY - A Fast Majority Vote Algorithm", 1982.