majority: Boyer-Moore Majority Vote Algorithm

[ algorithms, library, public-domain ] [ Propose Tags ]

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.


[Skip to Readme]

Modules

[Index]

Downloads

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

  • No Candidates
Versions [RSS] 1.0, 1.1
Dependencies haskell2010 [details]
License LicenseRef-PublicDomain
Author Nis N. Wegmann
Maintainer niswegmann@gmail.com
Category Algorithms
Home page https://github.com/niswegmann/majority
Source repo head: git clone https://github.com/niswegmann/majority.git
Uploaded by NisWegmann at 2011-07-18T15:57:23Z
Distributions
Reverse Dependencies 1 direct, 0 indirect [details]
Downloads 1871 total (6 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for majority-1.1

[back to package description]

Majority

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.

Install

Assuming you have installed the Haskell Platform use cabal:

$ cabal install majority

Bugs

Comments, bug reports, and patches will be much appreciated:

License

This library is distributed under a CC0 1.0 Universal Public Domain Dedication: