Abstract
In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Abrahamson, N. Dadoun, D. G. Kirkpatrick and T. Przytycka,A simple parallel tree contraction algorithm, Journal of Algorithms, vol. 10, 1989, pp. 287–302.
A. Aggarwalet al., Parallel computational geometry, Algorithmica, vol. 3, 1988, pp. 293–327.
S. G. Akl,Parallel Sorting Algorithms, Academic, Orlando, FL., 1985.
S. G. Akl,Parallel selection in O(log logn)time using O(n/log logn) processors, Technical Report. No. 221, Dept. of Computing and Information Science, Queen's University, Kingston, Ontario, March 1988.
A. V. Aho, J. E. Hopcroft and J. D. Ullman,The Design and Analysis of Computer Algorithms, Addison-Wesley Pub. Co., 1974.
M. J. Atallah and M. T. Goodrich,Efficient parallel solutions to some geometric problems, J. of Parallel and Distributed Computing, vol. 3, 1986, pp. 492–507.
D. Bitton, D. J. DeWitt, D. K. Hsiao and J. Menon,A taxonomy of parallel sorting, Computing Surveys, vol. 13, No. 3, 1984, pp. 287–318.
R. P. Brent,The parallel evaluation of general arithmetic expressions, J. ACM, vol. 21, 1974, pp. 201–206.
R. Cole,Parallel merge sort, SIAM J. Comput., vol. 17, No. 4, 1988, pp. 770–785.
R. Cole and U. Vishkin,Approximate and exact scheduling with applications to list, tree and graph problems, Proc. 27th Ann. IEEE Symp. on the Foundations of Computer Science, 1986, pp. 478–491.
L. Devroye,A note on the height of binary search trees, J. ACM, vol. 33, No. 3, 1986, pp. 489–498.
X. He and Y. Yesha,Binary tree algebraic computation and parallel algorithms for simple graphs, J. of Algorithms, vol. 9, 1988, pp. 92–113.
P. Heidelberger, A. Norton and J.T. Robinson,Parallel quicksort using fetch-and-add, IEEE Trans. on Computers, vol. 39, No. 1, 1990, pp. 133–138.
C. P. Kruskal,Algorithms for replace-add based paracomputers, Proc. of Intern. Conf. on Parallel Processing, 1982, pp. 219–223.
C. P. Kruskal, Larry Rudolph and Marc Snir,Efficient parallel algorithms for graph problems, Algorithmica, vol. 5, 1990, pp. 43–65.
C. U. Martel and D. Gusfield,A fast parallel quicksort algorithm, Information Processing Letters, vol. 30, Jan. 1989, pp. 97–102.
A. Moitra and S. S.Iyengar, A maximally parallel balancing algorithm for obtaining complete balanced binary trees, IEEE Trans. on Computers, vol. 34, No. 6, June, 1985, pp. 563–565.
A. Moitra and S. S. Iyengar,Derivation of a maximally parallel algorithm for balancing binary search tree, Dept. of Computer Science, Cornell University, Ithaca, NY, Tech. Rep. 84–638, Sept. 1984.
F. P. Preparata and M. I. Shamos,Computational Geometry — An Introduction, Springer-Verlag, 1989.
U. Vishkin,Implementation of simultaneous memory address access in models that forbid it, J. of Algorithms, vol. 4, 1983, pp. 45–50.
U. Vishkin,Synchronous parallel computation — A survey, Technical Report, No. 71, Dept. of Computer Science, Courant Institute, NYU, 1983.
Author information
Authors and Affiliations
Additional information
The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.
Rights and permissions
About this article
Cite this article
Zhang, W., Rao, N.S.V. Optimal parallel quicksort on EREW PRAM. BIT 31, 69–74 (1991). https://doi.org/10.1007/BF01952784
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01952784