On sorting in the presence of erroneous information
type: Item
instance of: scholarly article
title: On sorting in the presence of erroneous information
zbMATH Open document ID: 0763.68029
DOI: 10.1016/0020-0190(92)90203-8
author: S. Singh
published in: Information Processing Letters
publication date: 1993-01-17T00:00:00Z
review text: \textit{K. B. Lakshmanan}, \textit{B. Ravikumar} and \textit{K. Ganesan} [(*) Coping with erroneous information while sorting, IEEE Trans. Comput. 40(9), 1081-1084 (1991)] studied the following problem of sorting a given set \(X=\{x_ 1,x_ 2,\dots,x_ n\}\) of \(n\) distinct elements using binary comparisons of the form ``Is \(x_ i<x_ j\)?'', with two possible outcomes, ``yes'' and ``no'' for each comparison. However, some of the responses received for the comparisons could be erroneous. It is assumed that the number of errors can be at most \(e\), and \(e\) is known ahead of time. The authors established that if there are at most \(e\) erroneous responses, then the worst-case complexity of the sorting problem is \(\Omega(n\log n+en)\). They also presented an algorithm for the problem which requires at most \(O(n\log n+en+e^ 2)\) comparison queries. Clearly the algorithm is not optimal if \(e\) is large. We present an algorithm that uses at most \(O(n\log n+en)\) comparison queries, i.e. it matches the lower bound established in (*) for all values of \(e\).
Mathematics Subject Classification ID: 68P10
zbMATH DE Number: 96216
zbMATH Keywords: adversary strategy
zbMATH Keywords: binary insertion sort
zbMATH Keywords: errors
zbMATH Keywords: lies
zbMATH Keywords: two-person game
MaRDI profile type: Publication
full work available at URL: 0020-0190(92)90203-8
OpenAlex ID: W2000072121
cites work: Searching with a forbidden lie pattern in responses
cites work: Q3783955
cites work: Searching with known error probability
cites work: Q3773361
cites work: Coping with errors in binary search procedures
cites work: Q4121861
cites work: On Fault-Tolerant Networks for Sorting
description: scientific article; zbMATH DE number 96216