License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2023.8
URN: urn:nbn:de:0030-drops-183585
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18358/
Afshar, Ramtin ;
Dillencourt, Michael ;
Goodrich, Michael T. ;
Ozel, Evrim
Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors
Abstract
We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.
BibTeX - Entry
@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8,
author = {Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim},
title = {{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}},
booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)},
pages = {8:1--8:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-279-2},
ISSN = {1868-8969},
year = {2023},
volume = {265},
editor = {Georgiadis, Loukas},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18358},
URN = {urn:nbn:de:0030-drops-183585},
doi = {10.4230/LIPIcs.SEA.2023.8},
annote = {Keywords: sorting, algorithms, randomization, experimentation}
}
