On the expected lengths of sequences generated in sorting by replacement selecting

By William W. Hooker

Communications of the ACM, Vol. 12 No. 7, Pages 411-413
10.1145/363156.363189

In the replacement-selecting technique of sorting, one is interested in the ratio Lj of the expected length of the jth sequence generated by the technique to the number of memory cells used. Using complex-variable theory, it is shown that Lj → 2 and that, asymtotically, the average interval between sign changes of Lj — 2 is 2.6662.

The full text of this article is premium content

0 Comments

No entries found

Purchase the Article

On the expected lengths of sequences generated in sorting by replacement selecting

The full text of this article is premium content

0 Comments

Forgot your password?

Need Access?

Join the ACM

Subscribe to Communications of the ACM Magazine