Premium
A selection algorithm with a practical upper bound on expected number of comparisons
Author(s) -
Park Jong Soo,
Kim Myunghwan
Publication year - 1989
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380191107
Subject(s) - partition (number theory) , selection (genetic algorithm) , element (criminal law) , parametric statistics , mathematics , algorithm , distribution (mathematics) , upper and lower bounds , sample (material) , statistics , combinatorics , computer science , artificial intelligence , mathematical analysis , chemistry , chromatography , political science , law
A 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 be n + min( k, n‐k ) + O(n 2/3 ) through experimental tests where the sample size is approximately n 2/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 median.