Time bounds for selection. Blum, M., Floyd, R. W., Pratt, V., Rivest, R. L., & Tarjan, R. E. Journal of Computer and System Sciences, 7(4):448--461, August, 1973.
Time bounds for selection [link]Paper  doi  abstract   bibtex   
The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.
@article{blum_time_1973,
	title = {Time bounds for selection},
	volume = {7},
	issn = {0022-0000},
	url = {http://www.sciencedirect.com/science/article/B6WJ0-4RFMC9P-8/2/d76dbc78adcdd9951bf9acd46dc21eea},
	doi = {10.1016/S0022-0000(73)80033-9},
	abstract = {The number of comparisons required to select the i-th smallest of n numbers is shown to be at most a linear function of n by analysis of a new selection algorithm--PICK. Specifically, no more than 5.4305 n comparisons are ever required. This bound is improved for extreme values of i, and a new lower bound on the requisite number of comparisons is also proved.},
	number = {4},
	urldate = {2010-02-05TZ},
	journal = {Journal of Computer and System Sciences},
	author = {Blum, Manuel and Floyd, Robert W. and Pratt, Vaughan and Rivest, Ronald L. and Tarjan, Robert E.},
	month = aug,
	year = {1973},
	pages = {448--461}
}

Downloads: 0