A parallel algorithm is presented for selecting the kth smallest element of a totally ordered (but not sorted) set of n elements, 1⩽k⩽n. The algorithm uses n1−x processors and runs in O(nx) time, 0<x<1, for an optimal total cost of O(n).
Description
An optimal algorithm for parallel selection - ScienceDirect
%0 Journal Article
%1 AKL198447
%A Akl, Selim G.
%D 1984
%J Information Processing Letters
%K canada discovery emm parallel selection subgroup
%N 1
%P 47 - 50
%R https://doi.org/10.1016/0020-0190(84)90128-5
%T An optimal algorithm for parallel selection
%U http://www.sciencedirect.com/science/article/pii/0020019084901285
%V 19
%X A parallel algorithm is presented for selecting the kth smallest element of a totally ordered (but not sorted) set of n elements, 1⩽k⩽n. The algorithm uses n1−x processors and runs in O(nx) time, 0<x<1, for an optimal total cost of O(n).
@article{AKL198447,
abstract = {A parallel algorithm is presented for selecting the kth smallest element of a totally ordered (but not sorted) set of n elements, 1⩽k⩽n. The algorithm uses n1−x processors and runs in O(nx) time, 0<x<1, for an optimal total cost of O(n).},
added-at = {2018-06-03T14:55:32.000+0200},
author = {Akl, Selim G.},
biburl = {https://www.bibsonomy.org/bibtex/262315be4068e726285d3bc7528fe57a2/becker},
description = {An optimal algorithm for parallel selection - ScienceDirect},
doi = {https://doi.org/10.1016/0020-0190(84)90128-5},
interhash = {1c3e23c563b5f833b1e09e7e9fefd55e},
intrahash = {62315be4068e726285d3bc7528fe57a2},
issn = {0020-0190},
journal = {Information Processing Letters},
keywords = {canada discovery emm parallel selection subgroup},
number = 1,
pages = {47 - 50},
timestamp = {2018-06-03T14:55:32.000+0200},
title = {An optimal algorithm for parallel selection},
url = {http://www.sciencedirect.com/science/article/pii/0020019084901285},
volume = 19,
year = 1984
}