Philippine Science Letters
vol. 5 | no. 1 | 2012
published online January 30, 2012


ARTICLE


Average-case analysis of Leapfrogging samplesort


by Eliezer A. Albacea


Institute of Computer Science, University of the Philippines Los Baņos
College, Laguna, Philippines



FULL PDF VERSION

 



The leapfrogging samplesort was introduced in 1995 but was not analyzed completely. In this paper, we analyze the algorithm in terms of expected number of comparisons. In particular, we obtain an estimated expected number of comparisons of n [ log (n+1)] - 2 [ log (n+1) ] - n + [ log (n+1) ] + 1 comparisons using the assumption that we estimate instead the cumulative distribution function of the input sequence from a sample. It should be noted that the results obtained in this paper is an estimate of the true expected number of comparisons. The problem of getting the true expected number of comparisons remains open.


Email Address:
eaalbacea@uplb.edu.ph
Submitted: December 6, 2011
Accepted: December 27, 2011
Published: January 30, 2012
Editor-in-charge: Amador C. Muriel
Reviewer:
Amador C. Muriel