Sorting Networks
1. Comparator Networks : 와이어로 연결하여 정렬
- 구성 : wire, comparator
- comparator
예시)
이 때, depth(network 실행시간)는 아래 사진과 같이 3이다.
depth x,y = max(x,y) + 1
특징1) 0과 1로 이루어져 있을 때 올바르게 정렬되면, 0과 1 외의 숫자가 존재해도 올바르게 정렬될 수 있다.
특징2) 정렬하는 F(x)가 monotone increasing(증가함수)일 때, 항상 결과는 증가함수 y값으로 나온다.
2. Bitonic sorting network : 증-감, 또는 circular shift하면 증-감으로 만들 수 있는 것.
3. Half-cleaner
> depth 1
> compares input i with input i+n/2
: 정렬시 반쪽은 0 또는 1로 정렬되며, 다른 한쪽은 Bitonic으로 정렬 됨.
4. Bitonic-sorter[n]의 구성
> 1 half-clreaner[n]
> 2 bitonic-sorter[n/2]
depth D(n)
> 0 if n=1
> D(n/2)+1 if n=2 to the K
해 D(n) = log n
5. Merging network : Merging + Bitonic-Sorter
6. sorting network
> 2 Sorted[n/2]
> 1 Merger[n]
↓
