Communications of the ACM · 1975 · 280 citations · 4 references
Natural SciencesComputer ScienceMathematicsAlgorithmsOptimizationStatisticsSelection MethodsComparison ComplexityExpected-time AnalysisLower Bound ComputationLower Bound TechniquesLower Bound TheoremSelection AlgorithmsSelection Efficiency AssessmentWorst-case Bounds
A new selection algorithm is presented which is shown to be very efficient on the average, both theoretically and practically. The number of comparisons used to select the i th smallest of n numbers is n + min( i,n-i ) + o ( n ). A lower bound within 9 percent of the above formula is also derived.
4
Manuel Blum, Robert W. Floyd, Vaughan Pratt et al. · Journal of Computer and System Sciences · 1973 · 1.2K citations
Mathematical Analysis of Algorithms
Donald E. Knuth · IFIP Congress · 1971 · 119 citations
C. A. R. Hoare · Communications of the ACM · 1961 · 81 citations