Sorting is the task of ordering $n$ elements using pairwise comparisons. It is well known that $m=\Theta(n\log n)$ comparisons are both necessary and sufficient when the outcomes of the comparisons are observed with no noise. In this paper, we study the sorting problem in the presence of noise. Unlike the common approach in the literature which aims to minimize the number of pairwise comparisons $m$ to achieve a given desired error probability, we consider randomized algorithms with expected number of queries $\mathsf{E}[M]$ and aim at characterizing the maximal ratio $\frac{n\log n}{\mathsf{E}[M]}$ such that the ordering of the elements can be estimated with a vanishing error probability asymptotically. The maximal ratio is referred to as the noisy sorting capacity. In this work, we derive upper and lower bounds on the noisy sorting capacity. We establish two lower bounds, one for fixed-length algorithms and one for variable-length algorithms. The proposed algorithms exploit the connection between noisy searching and channel coding with feedback and incorporate the insertion sort algorithm with the Burnashev-Zigangirov algorithm for channel coding with feedback. Moreover, we derive an upper bound for the noisy sorting capacity and an upper bound for the achievable rates of algorithms based on insertion sort.
翻译:排序是使用对称比较来订购 $n 元元素的任务 。 众所周知, $m@ Theta( n\log n n) 比较在观测比较结果时是必要和足够的。 在本文中, 我们研究在噪音出现时的排序问题。 与文献中旨在尽量减少对称比较数量的通用方法不同 $m美元, 以达到预期的误差概率。 我们考虑随机化算法, 其预期查询数为$\mathsf{ E} [M] 。 我们考虑随机化算法, 并设定最大比值 $\frac{ nunmathsf{ E} 的特性。 如此, 当比较结果显示对元素的排序可以以消失的错误概率来估计。 最大比值是指杂音排序能力 。 在这项工作中, 我们从上下两个下限算法, 一个是固定长度算法, 一个是变量算法 。 拟议的算法, 利用在搜索和频道排序之间连接的连接,, 以及 将高级算算算算入一个可以实现的磁带的逻辑 。