Derivation of Randomized Sorting and Selection Algorithms
Derivation of Randomized Sorting and Selection Algorithms
复制标题
随机排序和选择算法的推导
DOI：
--
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
J. Reif
中科院分区：
文献类型：
--
作者：
S. Rajasekaran;J. Reif
在本文中，我们系统地推导出随机算法（顺序和并行）的排序和选择的基本原则和基本技术，如随机抽样。我们证明了几个采样引理，将找到独立的应用程序。这里导出的新算法是已知的最有效的。从其他结果中，我们有一个有效的算法顺序排序。
In this paper we systematically derive randomized algorithms (both sequential and parallel) for sorting and selection from basic principles and fundamental techniques like random sampling. We prove several sampling lemmas which will find independent applications. The new algorithms derived here are the most efficient known. From among other results, we have an efficient algorithm for sequential sorting.