二维网格上的一个快速并行分类算法  

A QUICK PARALLEL ALGORITHM FOR SORTING ON A TWO DIMENSION MESH

作　　者：罗晓广[1] 李晓梅[1] 

机构地区：[1]国防科学技术大学计算机系

出　　处：《计算机研究与发展》1997年第S1期71-75,共5页Journal of Computer Research and Development

摘　　要：文中采用递归分治的策略，构造了Ｎ×Ｎ网格上分类Ｎ个元素的一个快速并行算法．该算法总共需３Ｎ＋Ｏ（Ｎ１／３ｌｏｇＮ）步，每步至多做一次比较交换操作．由于Ｎ×Ｎ网格上的分类Ｎ个元素的并行算法的时间下界是３Ｎ－Ｏ（Ｎ）步，因此，该算法已近似地达到最优，而且直观简洁．Using the divide and conquer strategy recursively, a quick parallel algorithm for sorting N elements on a N×N mesh is presented. It needs totally 3 N+O(N 1/3 log N) steps. Each step includes one comparison and one exchange at most. Because a low bound of steps needed by sorting N elements on N×N mesh is 3 N-O(N ,the algorithm is nearly optimal.

关 键 词：并行分类算法 网格 0-1分类引理 剥夺算法 奇偶比较交换算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]