Expected time bounds for selection

DOI10.1145/360680.360691zbMath0296.68049OpenAlexW1989640573WikidataQ56337163 ScholiaQ56337163MaRDI QIDQ4050138

Ronald L. Rivest, Robert W. Floyd

Publication date: 1975

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/360680.360691

Mathematics Subject Classification ID

Algorithms in computer science (68W99)

Related Items (39)

On the median-of-k version of Hoare's selection algorithm ⋮ Select with Groups of 3 or 4 ⋮ SORTING AND SELECTION ON DISTRIBUTED MEMORY BUS COMPUTERS ⋮ Exploiting few inversions when sorting: Sequential and parallel algorithms ⋮ Finding the \(\alpha n\)-th largest element ⋮ A time warping approach to multiple sequence alignment ⋮ A Bayesian approach to relevance in game playing ⋮ Randomized algorithm for the sum selection problem ⋮ Geometric algorithms for the minimum cost assignment problem ⋮ Further analysis of the remedian algorithm ⋮ In-place linear probing sort ⋮ Some notes on robust sure independence screening ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Selection by distributive partitioning ⋮ Communication and energy efficient routing protocols for single-hop radio networks ⋮ Semantics of probabilistic programs ⋮ Unnamed Item ⋮ Weighted median algorithms for \(L_ 1\) approximation ⋮ Expected cost bounds for the selection and ordering procedures based on binary-type questions ⋮ BlockQuicksort ⋮ EFFICIENT ALGORITHMS FOR SELECTION AND SORTING OF LARGE DISTRIBUTED FILES ON DE BRUIJN AND HYPERCUBE STRUCTURES ⋮ Algorithms ⋮ Selection from read-only memory and sorting with minimum data movement ⋮ Parallel distributive partitioned sorting methods ⋮ Tardiness bounds under global EDF scheduling on a multiprocessor ⋮ Fast linear expected-time algorithms for computing maxima and convex hulls ⋮ Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses ⋮ Streaming Algorithms for Selection and Approximate Sorting ⋮ Finding a mediocre player ⋮ Sorting in linear time? ⋮ A selectable sloppy heap ⋮ Exponential bounds for the running time of a selection algorithm ⋮ Randomized selection in \(n+C+o(n)\) comparisons ⋮ Selection Algorithms with Small Groups ⋮ Galton, Edgeworth, Frisch, and prospects for quantile regression in econometrics ⋮ Random sampling and greedy sparsification for matroid optimization problems ⋮ Linear sorting with O(log n) processors ⋮ On Floyd and Rivest's SELECT algorithm ⋮ The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors

This page was built for publication: Expected time bounds for selection