Quick links

On Straight Selection Sort

Report ID:
TR-185-88
Authors:
Date:
September 1988
Pages:
73
Download Formats:
[PDF]

Abstract:

The expected value of Bn = B'n - (n - 1), where B'n is the number of right-to-left maxima encountered by the straight selection sort, is well known to be (n+1)Hn - 2n, but the variance of Bn has remained unanalyzed. In this paper, we derive an exact formula for the variance of Bn, and show that it is
asymptotically equal to alpha n3/2(1 + o(1)), where alpha > 0 is an explicitly defined constant.

Follow us: Facebook Twitter Linkedin