Case Study:快排序算法的并行化 算法5.2中描述了使用2m个处理器完成对n个输入数据 排序的并行算法 procedure para_quicksort(data,i,j,m,id) 算法52快速排序并行算法 Begin 输入：无序数组data[1,n],使用 (1)if (j-i)sk or m=o then 的处理器个数2m (1.1)P_id call quicksort(data,i,j) 输出：有序数组data[1,n] else Begin (1.2)P_id:r=partition(data,i,j) para_quicksort(data,1,n,m,o) (1.3)P_id send data[r+1,j]to P_id+2m-11 End (1.4)para_quicksort(data,i,r-1,m-1,id) (1.5)para_quicksort(data,r+1,j,m-1,id+2m-1-1) (1.6)P id+2T-1 send data[r+1,j]back to P id end if End 13 2011/10/18Case Study:快排序算法的并行化 13 2011/10/18 算法5.2中描述了使用2௠个处理器完成对n个输入数据 排序的并行算法. 算法5.2 快速排序并行算法 输入：无序数组data[1,n]，使用 的处理器个数2௠ 输出：有序数组data[1,n] Begin para_quicksort(data,1,n,m,0) End procedure para_quicksort(data,i,j,m,id) Begin (1)if (j‐i)≤k or m=0 then (1.1)P_id call quicksort(data,i,j) else (1.2)P_id: r=partition(data,i,j) (1.3)P_id send data[r+1,j] to P_id+2௠ିଵ‐1 (1.4)para_quicksort(data,i,r‐1,m‐1,id) (1.5)para_quicksort(data,r+1,j,m‐1,id+2௠ିଵ‐1) (1.6)P_id+2௠‐1 send data[r+1,j] back to P_id end if End