An Algorithm for the <I>K</I>-Selection Problem Using Special-Purpose Sorters

Heung-Shik KIM; Jong-Soo PARK; Myunghwan KIM

An Algorithm for the K-Selection Problem Using Special-Purpose Sorters

Heung-Shik KIM, Jong-Soo PARK, Myunghwan KIM

Full Text Views

0

Cite this

Summary :

An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.

Publication: IEICE TRANSACTIONS on Information Vol.E75-D No.5 pp.704-708

Publication Date: 1992/09/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Cite this

Copy

Heung-Shik KIM, Jong-Soo PARK, Myunghwan KIM, "An Algorithm for the K-Selection Problem Using Special-Purpose Sorters" in IEICE TRANSACTIONS on Information, vol. E75-D, no. 5, pp. 704-708, September 1992, doi: .
Abstract: An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.
URL: https://global.ieice.org/en_transactions/information/10.1587/e75-d_5_704/_p

Copy

@ARTICLE{e75-d_5_704,
author={Heung-Shik KIM, Jong-Soo PARK, Myunghwan KIM, },
journal={IEICE TRANSACTIONS on Information},
title={An Algorithm for the K-Selection Problem Using Special-Purpose Sorters},
year={1992},
volume={E75-D},
number={5},
pages={704-708},
abstract={An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - An Algorithm for the K-Selection Problem Using Special-Purpose Sorters
T2 - IEICE TRANSACTIONS on Information
SP - 704
EP - 708
AU - Heung-Shik KIM
AU - Jong-Soo PARK
AU - Myunghwan KIM
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E75-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - September 1992
AB - An algorithm is presented for selecting the k-th smallest element of a totally ordered (but not sorted) set of n elements, 1kn, in the case that a special-purpose sorter is used as a coprocessor. When the pipeline merge sorter is used as the special-purpose sorter, we analyze the comparison complexity of the algorithm for the given capacity of the sorter. The comparison complexity of the algorithm is 1.4167no(n), provided that the capacity of the sorter is 256 elements. The comparison complexity of the algorithm decreases as the capacity of the sorter increases.
ER -