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

Heung-Shik KIM  Jong-Soo PARK  Myunghwan KIM  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E75-D   No.5   pp.704-708
Publication Date: 1992/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
Keyword: 
algorithm,  coprocessor,  median,  selection,  special-purposesorter,  

Full Text: PDF(389.2KB)>>
Buy this Article




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.