On Straight Selection Sort
Report ID: TR-185-88Author: Yao, Andrew
Date: 1988-10-00
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.