A selection algorithm with a practical upper bound on expected number of comparisons

摘要

AbstractA selection algorithm to find the Irth smallest element of a elements is presented. The algorithm mainly consists of the partition procedure and an improved method to choose a partitioning element. The algorithm estimates the partitioning element from a small sample so that the icth element is contained in the smaller partition between two partitions resulting from partitioning. The partitioning element is determined by using estimation of the cumulative frequency distribution in the theory of non‐parametric statistics. The expected number of comparisons is found to ben+ min(k, n‐k) +O(n2/3) through experimental tests where the sample size is approximatelyn2/3. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the med