二次元配列に基づく分類網の構成に関する二,三の結果

概要

論文の詳細を見る
Many synthesis methods of sorting networks using comparators (C_2-cells) are usually estimated asymptotically by the number of C_2-cells required by these algorithms as functions of the number of inputs. Therefore, those methods give economical constructions for some special forms of the number of inputs(e.g. even powers of two(2^<2r>) in Van Voorhis'algorithm). In this paper, we investigate some conservative properties of patial ordering generated in the process of synthesis, and a synthesis algorithm is obtained by applying these properties. The number of C_2-cells required by this algorithm for 2^<2r+1> inputs as a function of the number of inputs has the same coefficients of the two governing terms as by Van Voohis'algorithm for 2^<2r> inputs. As another application, an algorithm suitable for the synthesis of sorting networks using 4-sorters as components isproposed and the number of C_4-cells required by this algorithm is derived as a function of the number of inputs.
一般社団法人情報処理学会の論文
1976-11-15