Mesh sorting and selection optimal on the average

被引：0
|
作者：
Chlebus, BS
机构：
来源：
COMPUTERS AND ARTIFICIAL INTELLIGENCE | 1997年 / 16卷 / 02期
关键词：
parallel algorithm; mesh-connected computer; average performance; optimal algorithm; sorting; selection;
D O I：
暂无
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
We consider 1-1 sorting and selection problems on an n x n mesh-connected processor arrays. Algorithms are developed which are fast with respect to the average-time performance. We show that selection can be accomplished in the average time n + o(n), and sorting in the average time 2.n + o(n). Matching lower bounds are also proved.
引用
收藏
页码：141 / 152
页数：12
相关论文
共 50 条
  • [21] Optimal Parallel Sorting with Comparison Errors
    Goodrich, Michael T.
    Jacob, Riko
    PROCEEDINGS OF THE 35TH ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES, SPAA 2023, 2023, : 355 - 365
  • [22] AN OPTIMAL PARALLEL ADAPTIVE SORTING ALGORITHM
    CARLSSON, S
    CHEN, JS
    INFORMATION PROCESSING LETTERS, 1991, 39 (04) : 195 - 200
  • [23] Optimal and practical algorithms for sorting on the PDM
    Rajasekaran, Sanguthevar
    Sen, Sandeep
    IEEE TRANSACTIONS ON COMPUTERS, 2008, 57 (04) : 547 - 561
  • [24] Improved Algorithm of C4.5 Decision Tree on the Arithmetic Average Optimal Selection Classification Attribute
    Nie, Bin
    Luo, Jigen
    Du, Jianqiang
    Peng, Lin
    Wang, Zhuo
    Chen, Ai
    2017 IEEE INTERNATIONAL CONFERENCE ON BIOINFORMATICS AND BIOMEDICINE (BIBM), 2017, : 1376 - 1380
  • [25] Optimal sorting in group contests with complementarities
    Brookins, Philip
    Lightle, John P.
    Ryvkin, Dmitry
    JOURNAL OF ECONOMIC BEHAVIOR & ORGANIZATION, 2015, 112 : 311 - 323
  • [26] Fast deterministic selection on mesh-connected processor arrays
    Krizanc, D
    Narayanan, L
    Raman, R
    ALGORITHMICA, 1996, 15 (04) : 319 - 331
  • [27] Decision trees with minimum average depth for sorting eight elements
    AbouEisha, Hassan
    Chikalov, Igor
    Moshkov, Mikhail
    DISCRETE APPLIED MATHEMATICS, 2016, 204 : 203 - 207
  • [28] Optimal parallel algorithms for multiselection on mesh-connected computers
    Shen, H
    Han, YJ
    Pan, Y
    Evans, DJ
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 2003, 80 (02) : 165 - 179
  • [29] Modification of a System Based on the Use of Selection and Sorting Markers for the Screening of Stable Transfectants
    I. G. Vorobyova
    R. R. Shukurov
    D. G. Kozlov
    T. B. Koryagina
    N. V. Antipova
    V. N. Stepanenko
    Applied Biochemistry and Microbiology, 2018, 54 : 842 - 848
  • [30] Modification of a System Based on the Use of Selection and Sorting Markers for the Screening of Stable Transfectants
    Vorobyova, I. G.
    Shukurov, R. R.
    Kozlov, D. G.
    Koryagina, T. B.
    Antipova, N. V.
    Stepanenko, V. N.
    APPLIED BIOCHEMISTRY AND MICROBIOLOGY, 2018, 54 (09) : 842 - 848
12345