A (fairly) simple circuit that (usually) sorts
作者： T. Leighton , C.G. Plaxton
关键词:
摘要: A natural k-round tournament over n=2/sup k/ players is analyzed, and it demonstrated that the possesses a surprisingly strong ranking property. The property of this exploited by being used as building block for efficient parallel sorting algorithms under variety different models computation. Three important applications are provided. First, circuit depth 7.44 log n, which sorts all but superpolynomially small fraction n-factorial possible input permutations, defined. Secondly, randomized algorithm runs in O(log n) word steps with very high probability given hypercube related computers (the butterfly, cube-connected cycles, shuffle-exchange). Thirdly, O(m+log n)-bit n O(m)-bit records on an n-node butterfly. >
sci-hub.se 参考文章(9)
M. Ajtai, J. Komlós, E. Szemerédi, Sorting inc logn parallel steps Combinatorica. ,vol. 3, pp. 1- 19 ,(1983) , 10.1007/BF02579338
John H. Reif, Leslie G. Valiant, A logarithmic time sort for linear size networks Journal of the ACM. ,vol. 34, pp. 60- 76 ,(1987) , 10.1145/7531.7532
Prabhakar Raghavan, Probabilistic construction of deterministic algorithms: Approximating packing integer programs 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). ,vol. 37, pp. 10- 18 ,(1986) , 10.1109/SFCS.1986.45
M. S. Paterson, Improved Sorting Networks with O(log n) Depth Algorithmica. ,vol. 5, pp. 75- 92 ,(1987) , 10.1007/BF01840378
B. Aiello, F. T. Leighton, B. Maggs, M. Newman, Fast algorithms for bit-serial routing on a hypercube acm symposium on parallel algorithms and architectures. pp. 55- 64 ,(1990) , 10.1145/97444.97459
Herman Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations Annals of Mathematical Statistics. ,vol. 23, pp. 493- 507 ,(1952) , 10.1214/AOMS/1177729330
M. Ajtai, J. Komlós, E. Szemerédi, An 0(n log n) sorting network symposium on the theory of computing. pp. 1- 9 ,(1983) , 10.1145/800061.808726
V. E. Beneš, Optimal Rearrangeable Multistage Connecting Networks Bell System Technical Journal. ,vol. 43, pp. 1641- 1656 ,(1964) , 10.1002/J.1538-7305.1964.TB04103.X
Donald Ervin Knuth, The Art of Computer Programming ,(1968)