In this paper, we examine the problem of stochastic sorting, which is also known as sorting with errors, or sorting under a stochastic environment. We introduce a new concept of filtering the stochastic "signals" using deterministic filters, which, in turn, attenuate any errors which occur during the comparison of individual pairs of values. We show that these deterministic filters, which can be used by standard sorting algorithms to achieve stochastic sorting, significantly increase the probability that the lists will be sorted correctly. We introduce two such filters called the Majority filter, and its optimized variant, the Optimal Majority filter. They have been compared for accuracy and computational complexity. More detailed comparisons which involves these and other deterministic filters, and their stochastic versions are found in [15]. Copyright 2004 ACM.

Additional Metadata
Persistent URL dx.doi.org/10.1145/986537.986591
Conference 42nd Annual Southeast Regional Conference, ACM-SE 42
Citation
Oommen, J, Zgierski, J.R. (Jack R.), & Nussbaum, D. (2004). Deterministic majority filters applied to stochastic sorting. Presented at the 42nd Annual Southeast Regional Conference, ACM-SE 42. doi:10.1145/986537.986591