Home → Magazine Archive → July 1969 (Vol. 12, No. 7) → On the expected lengths of sequences generated in... → Abstract

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

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


No entries found