首页    期刊浏览 2025年06月10日 星期二
登录注册

文章基本信息

  • 标题:Optimally Sorting Evolving Data
  • 作者:Juan Jose Besa ; William E. Devanny ; David Eppstein
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:107
  • 页码:81:1-81:13
  • DOI:10.4230/LIPIcs.ICALP.2018.81
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:We give optimal sorting algorithms in the evolving data framework, where an algorithm's input data is changing while the algorithm is executing. In this framework, instead of producing a final output, an algorithm attempts to maintain an output close to the correct output for the current state of the data, repeatedly updating its best estimate of a correct output over time. We show that a simple repeated insertion-sort algorithm can maintain an O(n) Kendall tau distance, with high probability, between a maintained list and an underlying total order of n items in an evolving data model where each comparison is followed by a swap between a random consecutive pair of items in the underlying total order. This result is asymptotically optimal, since there is an Omega(n) lower bound for Kendall tau distance for this problem. Our result closes the gap between this lower bound and the previous best algorithm for this problem, which maintains a Kendall tau distance of O(n log log n) with high probability. It also confirms previous experimental results that suggested that insertion sort tends to perform better than quicksort in practice.
  • 关键词:Sorting; Evolving data; Insertion sort
Loading...
联系我们|关于我们|网站声明
国家哲学社会科学文献中心版权所有