Short Note: Finding a majority when sorting is not available
Open Access
- 1 January 1991
- journal article
- Published by Oxford University Press (OUP) in The Computer Journal
- Vol. 34 (2) , 186
- https://doi.org/10.1093/comjnl/34.2.186
Abstract
Let the abstract data type Object support an equivalence relation. This paper contains a fast, simple, space-frugal algorithm to determine whether a majority of an arbitrary set of such Objects belong to the same equivalence class (are the ‘same’) even when no total order is available for sorting and even if there are infinitely many different equivalence classes.Keywords
This publication has 0 references indexed in Scilit: