Finding the median
From MaRDI portal
Publication:1229583
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
Analysis of algorithms and problem complexity (68Q25) Order statistics; empirical distribution functions (62G30) Total orders (06A05) Algorithms in computer science (68W99)
Related Items
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
