VOLUME 5 NUMBER 1 (January to June 2012)

Phil. Sci. Lett. 2013 5 (1) 014-016
available online: January 30, 2012

*Corresponding author
Email Address: eaalbacea@uplb.edu.ph
Submitted: December 6, 2011
Accepted: December 27, 2011


Average-case analysis of Leapfroggingsamplesort

by Eliezer A. Albacea

Institute of Computer Science, University of the Philippines Los Baños
College, Laguna, Philippines
The leapfrogging samplesort was introduced in1995 but was not analyzed completely. In thispaper, we analyze the algorithm in terms ofexpected number of comparisons. In particular,we obtain an estimated expected number ofcomparisons of n [ log (n+1)] - 2 [ log (n+1) ] - n + [ log (n+1) ]+ 1 comparisons using the assumption that we estimate insteadthe cumulative distribution function of the input sequence from asample. It should be noted that the results obtained in this paperis an estimate of the true expected number of comparisons. Theproblem of getting the true expected number of comparisonsremains open.

© 2017 Philippine Science Letters