Finding the median

DOI10.1016/S0022-0000(76)80029-3zbMath0335.68033OpenAlexW2273959428MaRDI QIDQ1229583

Arnold Schönhage, Nicholas J. Pippenger, Michael S. Paterson

Publication date: 1976

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0022-0000(76)80029-3

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Order statistics; empirical distribution functions (62G30) Total orders (06A05) Algorithms in computer science (68W99)

Related Items (45)

Selecting distances in the plane ⋮ Scheduling jobs with release dates and tails on identical machines to minimize the makespan ⋮ Select with Groups of 3 or 4 ⋮ Progress in selection ⋮ Optimal Parallel Algorithms For Multiselection On Mesh-Connected Computers ⋮ Near-optimal online multiselection in internal and external memory ⋮ An improved algorithm for finding the median distributively ⋮ Distributed algorithms for selection in sets ⋮ Finding the \(\alpha n\)-th largest element ⋮ On the upper bound of the complexity of sorting ⋮ Determining the mode ⋮ On the lower bound for minimum comparison selection ⋮ Architecture independent parallel selection with applications to parallel priority queues ⋮ Selection by distributive partitioning ⋮ Optimal sampling strategies for quicksort ⋮ Producing posets ⋮ Efficient searching using partial ordering ⋮ Unnamed Item ⋮ Bin packing can be solved within 1+epsilon in linear time ⋮ A note on upper bounds for the selection problem ⋮ Range Medians ⋮ Optimal parallel selection in sorted matrices ⋮ Heaps with bits ⋮ Unnamed Item ⋮ An optimal algorithm for \(2 \times{} n\) bottleneck transportation problems ⋮ Selection from read-only memory and sorting with minimum data movement ⋮ Faster suffix sorting ⋮ Necklaces, convolutions, and \(X+Y\) ⋮ An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees ⋮ On partial sorting in restricted rounds ⋮ The Min-Max Spanning Tree Problem and some extensions ⋮ Comparator networks for binary heap construction ⋮ Sorting by distributive partitioning ⋮ On the complexity of coupled-task scheduling ⋮ The double selection problem ⋮ Finding a mediocre player ⋮ 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 ⋮ Linear sorting with O(log n) processors ⋮ Comparator networks for binary heap construction ⋮ On Floyd and Rivest's SELECT algorithm ⋮ Analysis of a linear programming heuristic for scheduling unrelated parallel machines ⋮ The recursive structure of some ordering problems

Cites Work

• Time bounds for selection
• Unnamed Item

This page was built for publication: Finding the median