Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time
Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time
复制标题
Zig-zag 排序：一种简单的确定性数据忽略排序算法，运行时间为 O(n log n)
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
M. Goodrich
中科院分区：
文献类型：
--
作者：
M. Goodrich
我们描述的曲折排序-一个确定性的数据不经意的排序算法运行在O（n log n）的时间，可以说是简单的比以前已知的算法具有类似的属性，这是基于AKS排序网络。因为它是数据不经意和确定性的，所以曲折排序可以实现为一个简单的O（n log n）大小的排序网络，从而为Incerpi和Sedgewick在1985年提出的一个开放问题提供了解决方案。此外，Zig-zag Sort是Shellsort的一个变体，实际上是第一个在O（n log n）时间内运行的确定性Shellsort变体。Plaxton等人在1992年和Sedgewick在1996年提出了这样一个算法的存在性问题。与今天更相关的事实是，在O（n log n）时间内运行的简单数据不经意确定性排序算法的存在简化了几种提议的遗忘RAM模拟方法（其利用AKS排序网络）中的“内循环”计算，并且这反过来意味着在几种云计算应用中用于隐私保护数据外包的简化机制。
We describe Zig-zag Sort---a deterministic data-oblivious sorting algorithm running in O(n log n) time that is arguably simpler than previously known algorithms with similar properties, which are based on the AKS sorting network. Because it is data-oblivious and deterministic, Zig-zag Sort can be implemented as a simple O(n log n)-size sorting network, thereby providing a solution to an open problem posed by Incerpi and Sedgewick in 1985. In addition, Zig-zag Sort is a variant of Shellsort, and is, in fact, the first deterministic Shellsort variant running in O(n log n) time. The existence of such an algorithm was posed as an open problem by Plaxton et al. in 1992 and also by Sedgewick in 1996. More relevant for today is the fact that the existence of a simple data-oblivious deterministic sorting algorithm running in O(n log n) time simplifies the "inner-loop" computation in several proposed oblivious-RAM simulation methods (which utilize AKS sorting networks), and this, in turn, implies simplified mechanisms for privacy-preserving data outsourcing in several cloud computing applications.