https://scholars.lib.ntu.edu.tw/handle/123456789/624642
Title: | Sorting with recurrent comparison errors | Authors: | Geissmann B Leucci S Liu C.-H Penna P. CHIH-HUNG LIU |
Keywords: | Maximum and total dislocation; Recurrent comparison error; Sorting | Issue Date: | 2017 | Journal Volume: | 92 | Source: | Leibniz International Proceedings in Informatics, LIPIcs | Abstract: | We present a sorting algorithm for the case of recurrent random comparison errors. The algorithm essentially achieves simultaneously good properties of previous algorithms for sorting n distinct elements in this model. In particular, it runs in O(n2) time, the maximum dislocation of the elements in the output is O(log n), while the total dislocation is O(n). These guarantees are the best possible since we prove that even randomized algorithms cannot achieve o(log n) maximum dislocation with high probability, or o(n) total dislocation in expectation, regardless of their running time. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85038582404&doi=10.4230%2fLIPIcs.ISAAC.2017.38&partnerID=40&md5=49ce5a919d2fc43f23cf93180d0b9303 https://scholars.lib.ntu.edu.tw/handle/123456789/624642 |
ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.ISAAC.2017.38 | SDG/Keyword: | Errors; Sorting; Distinct elements; High probability; Randomized Algorithms; Running time; Sorting algorithm; Random errors |
Appears in Collections: | 電機工程學系 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.