Adaptive Shivers Sort: An Alternative Sorting Algorithm
Adaptive Shivers Sort: An Alternative Sorting Algorithm
复制标题
自适应颤抖排序：另一种排序算法
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Jugé
中科院分区：
文献类型：
--
作者：
V. Jugé
我们提出了一种新的排序算法，称为自适应ShiversSort，利用存在的单调运行有效地排序部分排序的数据。该算法是著名算法TimSort的变体，TimSort是在编程语言的标准库中使用的排序算法，例如Python或Java（用于非原始类型）。更确切地说，自适应ShiversSort是一种所谓的（k）感知合并排序算法，一类捕获“TimSort类”算法，由Buss和Knop引入。在这篇文章中，我们证明，虽然自适应Shiversort是简单的实现，并略有不同，从TimSort，其计算成本，在进行比较的数量，是最佳的类内的自然归并排序算法，一个小的添加剂线性项。这使得自适应ShifersSort成为第一个受益于此属性的（k）感知算法，这也比TimSort的最坏情况改进了33%。这表明自适应ShiversSort可能是替代TimSort的有力竞争者。然后，我们研究了（k）-感知算法的最优性。我们给出了最佳逼近因子的下限和上限，这样的算法，相比，最佳稳定的自然归并排序算法。特别是，我们设计的自适应ShiversSort的计算成本是最佳的任意小的乘法因子的泛化。
We present a new sorting algorithm, called adaptive ShiversSort, that exploits the existence of monotonic runs for sorting efficiently partially sorted data. This algorithm is a variant of the well-known algorithm TimSort, which is the sorting algorithm used in standard libraries of programming languages such as Python or Java (for non-primitive types). More precisely, adaptive ShiversSort is a so-called (k) -aware merge-sort algorithm, a class that captures “TimSort-like” algorithms and that was introduced by Buss and Knop. In this article, we prove that, although adaptive ShiversSort is simple to implement and differs only slightly from TimSort, its computational cost, in number of comparisons performed, is optimal within the class of natural merge-sort algorithms, up to a small additive linear term. This makes adaptive ShiversSort the first (k) -aware algorithm to benefit from this property, which is also a 33% improvement over TimSort’s worst-case. This suggests that adaptive ShiversSort could be a strong contender for being used instead of TimSort. Then, we investigate the optimality of (k) -aware algorithms. We give lower and upper bounds on the best approximation factors of such algorithms, compared to optimal stable natural merge-sort algorithms. In particular, we design generalisations of adaptive ShiversSort whose computational costs are optimal up to arbitrarily small multiplicative factors.