Some Results on the Number of Comparisons in Selection Algorithms
Summary :
Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).
- Publication
- IEICE TRANSACTIONS on transactions Vol.E59-E No.12 pp.17-18
- Publication Date
- 1976/12/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- Category
- Automata and Languages
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kohei NOSHITA, "Some Results on the Number of Comparisons in Selection Algorithms" in IEICE TRANSACTIONS on transactions,
vol. E59-E, no. 12, pp. 17-18, December 1976, doi: .
Abstract: Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e59-e_12_17/_p
Copy
@ARTICLE{e59-e_12_17,
author={Kohei NOSHITA, },
journal={IEICE TRANSACTIONS on transactions},
title={Some Results on the Number of Comparisons in Selection Algorithms},
year={1976},
volume={E59-E},
number={12},
pages={17-18},
abstract={Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).},
keywords={},
doi={},
ISSN={},
month={December},}
Copy
TY - JOUR
TI - Some Results on the Number of Comparisons in Selection Algorithms
T2 - IEICE TRANSACTIONS on transactions
SP - 17
EP - 18
AU - Kohei NOSHITA
PY - 1976
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E59-E
IS - 12
JA - IEICE TRANSACTIONS on transactions
Y1 - December 1976
AB - Several basic properties of minimum-comparison selection algorithms are shown, and some exact values are obtained for Vt(n) for small n, where Vt(n) denotes the number of comparisons necessary to select the t-th largest of n elements. The upper bound for V5(10) is reduced to 16. Those results improve the table of the best upper bounds known for Vt(n) in the Knuth's book (Sorting and Searching).
ER -
English
