无存储器冲突的并行快速排序算法<sup>*</sup>

管丽

引用本文:	管丽.无存储器冲突的并行快速排序算法^*.软件学报,1996,7(zk):249-253

【打印本页】【下载PDF全文】【查看/发表评论】【EndNote】【RefMan】【BibTex】

←前一篇|后一篇→

过刊浏览高级检索

本文已被：浏览 4249次下载 5020次	码上扫一扫！
分享到：微信更多字体:加大+\|默认\|缩小-
无存储器冲突的并行快速排序算法^*
管丽¹
北京师范大学北京100875

摘要:

本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法，这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序．所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是 O(nlogn)．

关键词: 并行算法，排序算法，快速排序算法．

DOI：

分类号:

基金项目:

PARALLEL QUICKSORT WITHOUT MEMORY CONFLICTS

Guan Li

Abstract:

A parallel quicksort algorithm is given and which，given an EREW PRAM with k processors，sorts n items in expected O((n/k+logn)logn)time．and thus the prod-uct of time and number of processors is O(nlogn)on the average for any value ofk≤n/(logn)．

Key words: Parallel algorithm,sorting algorithm,parallel quicksort algorithm．