Abstract | ||
---|---|---|
In this paper(1), we examine the problem of stochastic sorting, which is also known as sorting with errors, or sorting under a stochastic environment. We extend an earlier-introduced concept of filtering the stochastic "signals" using deterministic filters [17], which, in turn, attenuate any errors which occur during the comparison of individual pairs of values. We show that these deterministic litters, which can be used by standard sorting algorithms to achieve stochastic sorting, significantly increase the probability that the lists will be sorted correctly. In this paper, we introduce two new deterministic filters called the Consecutive filter, and the Leader filter. They have been compared for accuracy, and for the amount of additional computation required in their implementations. More detailed comparisons which involves these and other deterministic filters, and their stochastic versions are found in the unabridged version of this paper [16]. |
Year | Venue | Field |
---|---|---|
2004 | MSV'04 & AMCS'04, PROCEEDINGS | Computer science,Algorithm,Sorting |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
1 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
B. John Oommen | 1 | 1255 | 222.20 |
Jack R. Zgierski | 2 | 0 | 0.68 |
Doron Nussbaum | 3 | 89 | 13.49 |