Selection from Read-Only Memory and Sorting with Minimum Data Movement
Selection from Read-Only Memory and Sorting with Minimum Data Movement
复制标题
从只读存储器中进行选择并以最少的数据移动进行排序
DOI：
10.1016/0304-3975(95)00225-1
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Venkatesh Raman
中科院分区：
文献类型：
--
作者：
J. Munro;Venkatesh Raman
选择给定秩的元素，例如中位数，是数据组织中的一个基本问题，也是基于比较的问题的计算复杂性。在这里，我们考虑的情况下，数据驻留在一个数组的只读存储器，因此元素不能在数组中移动。在这个模型下，我们开发了高效的选择算法，使用非常少的额外空间（o（logn）额外的存储单元）。这些算法包括O（n1 + ε）最坏情况算法和O（nloglogn）平均情况算法，两者都使用恒定数量的额外存储单元或索引。我们的算法补充了由Munro和Paterson [9]和Frederickson [4]获得的时空权衡的上界，他们开发了当Ω（（log n）2）额外存储单元可用时在同一模型中进行选择的算法。我们应用我们的选择算法来获得排序算法，该算法在任何给定的数组上执行最少数量的数据移动。我们还推导出最小的数据移动排序的时间-空间权衡的上限。
Selecting an element of given rank, for example the median, is a fundamental problem in data organization and the computational complexity of comparison based problems. Here, we consider the scenario in which the data resides in an array of read-only memory and hence the elements cannot be moved within the array. Under this model, we develop efficient selection algorithms using very little extra space (o(logn) extra storage cells). These include an O(n1 + ε) worst case algorithm and an O(nloglogn) average case algorithm, both using a constant number of extra storage cells or indices. Our algorithms complement the upper bounds for the time-space tradeoffs obtained by Munro and Paterson [9] and Frederickson [4] who developed algorithms for selection in the same model when Ω((log n)2) extra storage cells are available. We apply our selection algorithms to obtain sorting algorithms that perform the minimum number of data moves on any given array. We also derive upper bounds for time-space tradeoffs for sorting with minimum data movement.