一类新的并行排序算法(英文)

A Class of New Parallel Sorting Algorithms

提出了两种新的并行排序算法,在第一部分设计了一种有效的异步并行算法,可应用于多指令和多数据流计算机,且提供了该算法的最小和最大的运算时间.第二部分给出了一种新的并行排序网络,对于n个元素的排序序列,可以使用n(n-1) 2个比较元素和n(n-1) 2个反转换元素及n个转换元素能达到常数数量级的运行时间进行快速排序,同时给出了以{0,1}元素组成的序列的排序过程.

We present two new parallel sorting algorithms.In first chapter an efficient asynchronous parallel sorting algorithm on an MIMD computer has been designed.A lower bound and upper bound for running times of the algorithm are provided. In second chapter,a new parallel sorting network has been designed.By using n(n-1)/2 comparison elements,n(n-1)/2 inverters and n transverters which can with it perform the sum of {0,1}elements a fast sorting algorithm with a running time of T(n)=4 for the problem of sorting a sequence of n items has been proposed.