文档介绍：Parallel Algorithms Chapter 3 Sorting and Selection on Comparison Network
2020/12/9
精选PPT
主要内容
Batcher归并和排序
比较操作和[0, 1]原理
奇偶归并网络
双调归并网络
Batcher排序网络
(m, n)-选择网络
分组选择网络
平衡分组选择网络
2020/12/9
精选PPT
Batcher归并和排序
比较操作和[0, 1]原理
奇偶归并网络
双调归并网络
Batcher排序网络
2020/12/9
精选PPT
比较操作和[0,1]原理
1. Batcher比较器
比较和条件交换操作: CCI
比较器网络：用Batcher比较器连成的，完成某一功能的网络
假定：每次每个元素只能与另一个元素比较
比较器网络的参数：比较器数目、延迟级数
2020/12/9
精选PPT
比较操作和[0,1]原理
2. [0, 1]原理():
如果一个n输入的网络能排序所有2n种0,1序列，
那么它也能排序n个数的任意序列。
2020/12/9
精选PPT
奇偶归并网络
1. 网络构造
有序序列A:a1,a2,…,an
B: b1,b2,…,bm
归并思想：
A, B中奇数号元素进入奇归并器；
A, B中偶数号元素进入偶归并器；
再将奇归并器与偶归并器的输出进行交叉比较
注: (m,n)规模划分为：
2020/12/9
精选PPT
奇偶归并网络
2. 例：m=n=4 A=(2,4,6,8) B=(0,1,3,5)
(4, 4)奇偶归并2×(2, 2)奇偶归并＋1级交叉比较
(2,2)奇归并
2
4
6
8
0
1
3
5
2
0
6
3
4
1
8
5
0
2
3
6
1
4
5
8
0
2
3
6
1
4
5
8
0
1
2
3
4
5
6
8
(2,2)偶归并
1级交叉比较
2020/12/9
精选PPT
奇偶归并网络
3. 复杂性分析
比较器个数
Knuth ==>
当m=n=2t时，不难推得
2020/12/9
精选PPT
奇偶归并网络
3. 复杂性分析
延迟级数：穿过网络任一路线上的最多比较器数目
一般地有
当m=n=2t时，不难推得
2020/12/9
精选PPT
双调归并网络
1. 定义及定理
: 一个序列a1,a2,…,an是双调序列(Bitonic Sequence)，如果：
(1)存在一个ak(1≤k≤n), 使得a1≥…≥ak≤…≤an成立；或者
(2)序列能够循环移位满足条件(1)
示例：
序列(1,3,5,7,8,6,4,2,0), (7,8,6,4,2,0,1,3,5)和(1,2,3,4,5,6,7,8)
都是双调序列。 ak
(Batcher定理)：
设序列a1,…,an,an+1,…, a2n是一个双调序列, 记
bi=min{ai, ai+n} ==> MIN={b1,…,bn},
ci=max{ai, ai+n} ==> MAX={c1,…,cn}, 则
(1) bi≤cj (1≤i, j≤n) (2) MIN和MAX序列仍是双调的
2020/12/9
精选PPT