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 条
  • [1] Randomized routing, selection, and sorting on the OTIS-mesh
    Rajasekaran, S
    Sahni, S
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1998, 9 (09) : 833 - 840
  • [2] Scalable algorithms for the mesh with buses: Merging, sorting and selection
    Ramnath, S
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1998, 69 (1-2) : 17 - 32
  • [3] ALGORITHMS AND AVERAGE TIME-BOUNDS OF SORTING ON A MESH-CONNECTED COMPUTER
    GU, QP
    GU, J
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (03) : 308 - 315
  • [4] SORTING AND SELECTION IN POSETS
    Daskalakis, Constantinos
    Karp, Richard M.
    Mossel, Elchanan
    Riesenfeld, Samantha J.
    Verbin, Elad
    SIAM JOURNAL ON COMPUTING, 2011, 40 (03) : 597 - 622
  • [5] Sorting and Selection with Imprecise Comparisons
    Ajtai, Miklos
    Feldman, Vitaly
    Hassidim, Avinatan
    Nelson, Jelani
    ACM TRANSACTIONS ON ALGORITHMS, 2016, 12 (02)
  • [6] Energy efficient sorting, selection and searching
    Jayapaul, Varunkumar
    Jo, Seungbum
    Palem, Krishna V.
    Satti, Srinivasa Rao
    THEORETICAL COMPUTER SCIENCE, 2024, 1002
  • [7] Signaling and optimal sorting
    Timothy Perri
    Journal of Economics, 2019, 126 : 135 - 151
  • [8] Signaling and optimal sorting
    Perri, Timothy
    JOURNAL OF ECONOMICS, 2019, 126 (02) : 135 - 151
  • [9] EFFICIENT ALGORITHMS FOR PARALLEL SORTING ON MESH MULTICOMPUTERS
    SINGH, V
    KUMAR, V
    AGHA, G
    TOMLINSON, C
    INTERNATIONAL JOURNAL OF PARALLEL PROGRAMMING, 1991, 20 (02) : 95 - 131
  • [10] SORTING AND ROUTING ON OTIS-MESH OF TREES
    Lucas, Keny T.
    Jana, Prasanta K.
    PARALLEL PROCESSING LETTERS, 2010, 20 (02) : 145 - 154
12345