Probabilistic Parallel Algorithms for Sorting and Selection

DOI10.1137/0214030MaRDI QIDQ3700837zbMATH OpenOpenAlexFDO

Authors Rüdiger Reischuk

Publication date 1985

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0214030

zbMATH Keywords

decision treesparallel computationprobabilistic computationparallel random access machinesdegree of parallelism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 4201596
• scientific article; zbMATH DE number 4213428
• scientific article; zbMATH DE number 4037239
• Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms
• scientific article; zbMATH DE number 176084
• scientific article; zbMATH DE number 1304350
• A parallel selection algorithm
• Publication:4942231
• scientific article; zbMATH DE number 1302200
• scientific article; zbMATH DE number 4082988

Cited in

(41)

• scientific article; zbMATH DE number 1419211 (Why is no real title available?)
• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Finding an approximate median with high probability in constant parallel time
• Parallel algorithms for partitioning sorted sets and related problems
• The probabilistic method yields deterministic parallel algorithms
• On parallel integer sorting
• Architecture independent parallel selection with applications to parallel priority queues
• Faster deterministic sorting through better sampling.
• Sorting in rounds
• Fast deterministic selection on mesh-connected processor arrays
• Sorting numbers using limited systolic coprocessors
• The average-case parallel complexity of sorting
• Sorting, Approximate Sorting, and Searching in Rounds
• The queue-read queue-write asynchronous PRAM model
• Sorting and Selection with Random Costs
• Sorting strings and constructing digital search trees in parallel
• Parallel complexity of sorting problems
• Randomized multipacket routing and sorting on meshes
• Parallel selection
• An improved, randomized algorithm for parallel selection with an experimental study
• A randomized sorting algorithm on the BSP model
• A probabilistic analysis of the Floyd–Rivest expected time selection algorithm
• Probabilistic analysis of a grouping algorithm
• Parallel Selection with High Probability
• Heap construction in the parallel comparison tree model
• Sorting and Selecting in Rounds
• Parallel algorithms for select and partition with noisy comparisons
• PERMUTATION ROUTING AND SORTING ON THE RECONFIGURABLE MESH
• Probabilistic integer sorting
• A time-randomness tradeoff for selection in parallel
• Randomized range-maxima in nearly-constant parallel time
• scientific article; zbMATH DE number 4201596 (Why is no real title available?)
• Fast and optimal simulations between CRCW PRAMs
• scientific article; zbMATH DE number 1857638 (Why is no real title available?)
• On Floyd and Rivest's SELECT algorithm
• On Synchronous Parallel Computations with Independent Probabilistic Choice
• SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS
• Beyond the worst-case bisection bound: Fast sorting and ranking on meshes
• Hybridsort revisited and parallelized
• scientific article; zbMATH DE number 3978375 (Why is no real title available?)
• Efficient parallel algorithms for computing all pair shortest paths in directed graphs

This page was built for publication: Probabilistic Parallel Algorithms for Sorting and Selection

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