Probabilistic Parallel Algorithms for Sorting and Selection

DOI10.1137/0214030zbMATH Open0578.68040OpenAlexW2033191517MaRDI QIDQ3700837FDOQ3700837

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

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

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)

Cited In (41)

• The Average Complexity of Deterministic and Randomized Parallel Comparison-Sorting Algorithms
• Parallel algorithms for partitioning sorted sets and related problems
• Finding an approximate median with high probability in constant parallel time
• 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, Approximate Sorting, and Searching in Rounds
• Sorting and Selection with Random Costs
• Sorting numbers using limited systolic coprocessors
• The average-case parallel complexity of sorting
• The queue-read queue-write asynchronous PRAM model
• Sorting strings and constructing digital search trees in parallel
• Parallel complexity of sorting problems
• Parallel selection
• Randomized multipacket routing and sorting on meshes
• 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
• A time-randomness tradeoff for selection in parallel
• Probabilistic integer sorting
• Randomized range-maxima in nearly-constant parallel time
• Fast and optimal simulations between CRCW PRAMs
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Hybridsort revisited and parallelized
• Title not available (Why is that?)
• 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)