Sorting Networks

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]

↓