Eliezer A. Albacea
Institute of Computer Science, University of the Philippines Los Baños
doi.org/10.57043/transnastphl.1997.5924
Abstract
Blum, et. al. [1] presented a selection algorithm that finds the kth smallest element of a set with n distinct elements using 5.4305n comparisons in the worst case. In this paper, we present an improvement of this algorithm that requires 5.3975n comparisons in the worst case. The contribution of this paper is not on the amount of improvement but rather on the result that the worst case of the best practical algorithm for selection can still be improved. Thus. opening the possibility of further closing the gap between the best practical worst case and the best theoretical worst case for selection.