Publication IEICE TRANSACTIONS on Information and SystemsVol.E75-DNo.5pp.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)>>

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.