2001/03/28 by Greg Sepesi, Sepesi, Greg
Computer Science · Engineering · #Advanced Algorithms and Applications #Advanced Control Systems Design #Data Structures and Algorithms (cs.DS) #Distributed #E.1 #F.2.2 #FOS: Computer and information sciences #Fault Detection and Control Systems #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0103023
6 pages, 13 figures
arxiv created 2001/03/28 · openalex publication_date 2001/03/28 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An algorithm is presented that efficiently solves the selection problem: finding the k-th smallest member of a set. Relevant to a divide-and-conquer strategy, the algorithm also partitions a set into small and large valued subsets. Applied recursively, this partitioning results in a sorted set. The algorithm's applicability is therefore much broader than just the selection problem. The presented algorithm is based upon R.W. Floyd's 1964 algorithm that constructs a heap from the bottom-up. Empirically, the presented algorithm's performance appears competitive with the popular quickselect algorithm, a variant of C.A.R. Hoare's 1962 quicksort algorithm. Furthermore, constructing a heap from the bottom-up is an inherently parallel process (processors can work independently and simultaneously on subheap construction), suggesting a performance advantage with parallel implementations. Given the presented algorithm's broad applicability, simplicity, serial performance, and parallel nature, further study is warranted. Specifically, worst-case analysis is an important but still unsolved problem.