Selection Algorithms with Small Groups

DOI10.1142/S0129054120500136zbMATH Open1458.68292arXiv1409.3600OpenAlexW3023681931MaRDI QIDQ4983545FDOQ4983545

Adrian Dumitrescu, Ke Chen

Publication date: 20 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: We revisit the selection problem, namely that of computing the $i$th order statistic of $n$ given elements, in particular the classic deterministic algorithm by grouping and partition due to Blum, Floyd, Pratt, Rivest, and Tarjan (1973). Whereas the original algorithm uses groups of odd size at least $5$ and runs in linear time, it has been perpetuated in the literature that using smaller group sizes will force the worst-case running time to become superlinear, namely $Omega(nlogn)$. We first point out that the usual arguments found in the literature justifying the superlinear worst-case running time fall short of proving this claim. We further prove that it is possible to use group size smaller than $5$ while maintaining the worst case linear running time. To this end we introduce three simple variants of the classic algorithm, the repeated step algorithm, the shifting target algorithm, and the hyperpair algorithm, all running in linear time.

Full work available at URL: https://arxiv.org/abs/1409.3600

zbMATH Keywords

median selectioncomparison algorithm\(i\)th-order statistic

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40)

Cites Work

• Fast Deterministic Selection
• Title not available (Why is that?)
• Title not available (Why is that?)
• Probability and Computing
• Optimal parallel selection has complexity O(log log N)
• Time bounds for selection
• Title not available (Why is that?)
• On lower bounds for selecting the median
• The Ultimate Planar Convex Hull Algorithm?
• Title not available (Why is that?)
• Average case selection
• Expected time bounds for selection
• Partitioning with two lines in the plane
• Finding the median
• A Unified Lower Bound for Selection and Set Partitioning Problems
• Bounds for Selection
• A Counting Approach to Lower Bounds for Selection Problems
• Progress in selection
• Title not available (Why is that?)
• Selecting the Median
• New upper bounds for selection
• Title not available (Why is that?)
• Finding the \(\alpha n\)-th largest element
• A New Lower Bound for the Set-Partitioning Problem
• Closing a Long-Standing Complexity Gap for Selection: V 3(42) = 50
• On the Average-Case Complexity of Selecting the kth Best

Cited In (2)

• Title not available (Why is that?)
• Finding a mediocre player

Uses Software

• Find
• MedianOfNinthers

   Recommendations

• An algorithm for a selection procedure 👍 👎
• An optimally efficient selection algorithm 👍 👎
• Optimal subgroup selection 👍 👎
• New algorithms for selection 👍 👎
• Selection problem with applications 👍 👎
• A random-size subset approach to the selection problem 👍 👎
• Choice via grouping procedures 👍 👎
• Optimal partitioning of groups in selecting the best choice 👍 👎

This page was built for publication: Selection Algorithms with Small Groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4983545)