Bitonic sort

Bitonic sort는 병렬 처리의 이점을 활용할 수 있는 sorting 알고리즘이다.

https://en.wikipedia.org/wiki/Bitonic_sorter#/media/File:BitonicSort1.svg

그림은 다소 복잡해보이나 몇 단계로 나눠 이해하면 크게 어렵지 않다.

먼저 파란색/초록색 블럭이 있는 열을 stage라고 명하며, 붉은색 블록이 있는 열은 pass라고 부른다.

Stage는 파란색과 초록색의 블럭으로 이루어져있으며, 홀수의 블럭은 파란색, 짝수의 블럭은 초록색을 가진다.

Pass의 개수가 stage의 번호가 될 것이다.

각 pass 에는 화살표가 있으며, 화살표의 시작점에 있는 수와 화살표가 가리키는 수를 비교하여 큰수와 작은 수를 비교하고 바꾸게 된다. 화살표는 파란색 stage에서는 내림차순, 초록색 stage에서는 오름차순으로 정렬된다.

화살표가 가르키는 거리는 gap이 되며, 1<<(stage-pass) 가 gap의 값이 될 것이다.

예로 3번째 stage에서 파란색 블록의 경우, 3개의 pass를 가지며, 첫 번째 pass는 1<<(3-1) = 4 로 4의 gap을 가진다. 즉 4개 떨어진 숫자와 비교하여 내림차순 정렬을 하게된다. 마찬가지로 두 번째 pass는 1<<(3-2) = 2 로 2개 떨어진 숫자와 비교하게 된다.

각 stage가 진행되면서 stage의 블럭이 1개가 될 때 위 알고리즘을 종료하며, 즉 stage의 개수는 N개의 item이 있을 때 logN 개가 된다.

어떻게 수가 정렬되는지는 pass를 관찰해 보면 알 수 있다. 파란색의 블록만 생각할 때, pass 처음에 stage가 가지고 있는 item을 반으로 나눠 두 그룹 중 내림차순으로 정렬을 진행한다. 다음 pass에서는 그 두 그룹을 다시 반으로 각각 나누어 그 안에서 내림차순을 진행한다. Stage에서 pass가 모두 진행되면 그 결과는 해당 stage 의 item들이 모두 내림차순으로 정렬된 것을 알 수 있을 것이다.

실제로 숫자를 넣어보면, 

위와 같이 될 것이다.

특이한 점은 파란색 블록의 stage가 끝나면 해당 블록은 내림차순으로 정렬되어 있으며, 초록색 블록의 경우 오름차순으로 정렬된다. 다음 stage에서는 해당 조합이 다시 큰 블럭으로 내림차순 또는 오름차순으로 정렬되게 될 것이다. 내림차순과 오름차순이 반복되어 정렬되며 이러한 특성으로 bitonic (어떠한 기점으로 증가와 감소가 반복하는 형태) sort라고 불린다.

 

    std::vector<int> items;    
    // put items
 
    int N = items.size();
    int max_stage = log2(N);
    for (int stage = 0; stage < max_stage; stage++)
    {
        for (int pass = 0; pass <= stage; pass++)
        {
            int gap = 1 << (stage - pass);
 
            for (uint i = 0; i<sorted.size(); i++)
            {
                bool bOdd_block = ((i >> stage) & 2) == 0;
                // We don't need to compare and swap the lower-half parts of pass
                // because we already swap while comparing uppper-half of pass
                // i&gap == 0 means the i'th item is in upper-half of pass
                if (i&gap == 0)
                {
                    if ((bOdd_block && (items[i] > items[i+gap]) || (!bOdd_block && (items[i] < items[i+gap] )
                        swap(items[i], items[i+gap];
                }
            }
        }
    }

 

 

Proof of iterative rule for bitonic sorters

이 문단은 bitonic인 sequence $a_1, a_2, a_3, ..., a_{2n}$ 이 있고 다음과 같이 2개의 sequence (1), (2)가 있을 때

$min(a_1, a_{n+1}), min(a_2, a_{n+2}), ..., min(a_n, a_{2n})$               (1)

$max(a_1, a_{n+1}), max(a_2, a_{n+2}), ..., max(a_n, a_{2n})$              (2)

2개의 sequence는 모두 bitonic 이며 (1)에 속해있는 모든 수는 (2)에 속해있는 아무 숫자보다 작다는 것을 증명한다.

$1 \leq i \leq n$일 때 $d_i = min(a_i, a_n+i)$ 이며, $e_i = max(a_i, a_n+i)$ 라고 가정하자. 이 경우 $d_1, d_2, ..., d_n$ 과 $e_1, e_2, ..., e_n$이 bitonic 이며, 

$max(d_1, d_2, ..., d_n) \leq min(e_1, e_2, ..., e_n)$            (3)

인 것을 증명해야 한다.

$a_1, a_2, a_3, ..., a_{2n}$ 를 2개로 쪼갠다면 해당 부분들은 $d_i$ 와 $e_i$가 섞여있는 sequence가 될 것이다.

이는 bitonic 속성이나 식 (3)에 영향을 미치지 않기 때문에 $j(1\leq j \leq {2n})$일 때 

$a_1 \leq a_2 \leq a_3 \leq ... \leq a_{j-1} \leq a_j \geq a_{j+1} \geq ... \geq a_{2n} $       (4)

이 참이되는 경우에만 증명하여도 충분하다. (?? 일단 (4)에 대해서 (3)이 참이 되는 경우인지만 증명해보자)

(4)에서 sequence가 역으로 있는 경우 ($a'_i = a_{2n-i}$)에서도 bitonic 성질이 변하거나 maximum 또는 minimum의 값이 변하지 않으므로 $n < j \leq 2n$. 라고 가정해도 이를 증명하기 충분하다.

만약 $a_n \leq a_{2n}$이라면, $a_i \leq a_{n+i}$가 된다. $a_1$부터 $a_j$까지가 오름차순이고, $a_j$부터 $a_{2n}$까지가 내림차순인데, $a_n$이 $a_{2n}$보다 작을 경우 $a_{n+1}$에서 $a_j$까지는 모두 $a_n$보다 클 것이고, 마찬가지로 $a_j$부터 $a_{2n-1}$까지는 $a_{2n}$보다 클 것이기 때문이다. 따라서 이 경우 $d_i = a_i$, $e_i = a_{n+i}$ 를 만족하며 결국 값의 변화 없이 이전 sequence 상태와 동일한 상태가 될 것이다.

반대로 $a_n > a_{2n}$인 경우, $a_{j-n} \leq a_j$ 가 될 것이며, $j \leq k < 2n$, $a_{k-n} \leq a_k $, $a_{k-n+1} > a_{k+1}$ 세가지를 모두 만족하는 $k$를 찾을 수 있다.

이 경우 $a_1$에서 $a_j$까지는 오름차순이며, $a_{k-n} \leq a_{k}$ 이므로 

for $1 \leq i \leq k-n$  $\begin{cases} d_i = a_i \\ e_i = a_{i+n} \end{cases} $         (5)

for $k-n \leq i \leq n$  $\begin{cases} d_i = a_{i+n} \\ e_i = a_i \end{cases} $        (6)

을 만족하게 된다.

위 상황에서 $1 \leq i \leq k-n$에 해당하는 구역까지는 seqeunce의 변화가 없을 것이므로

$d_i \leq d_{i+1}$ for $1 \leq i \leq k-n$

를 만족 할 것이며, (6)에 따라 $k-n \leq i \leq n$ 부터는 $d_i$는 내림차순이던 $a_{i+n}$가 되므로 

$d_i \geq d_{i+1}$ for $k-n \leq i \leq n$

을 만족할 것이다. 따라서 $d_i$ sequence는 bitonic을 만족하게 된다.

$k-n \leq i \leq n$ 에서는 $e_i$는 결국 $a_i$가 될 것이며 이부분은 오름차순이기에

$e_i \leq e_{i+1}$ for $k-n \leq i \leq n$

가 되며, $1 \leq i < j-n$ 영역에서도  $e_i$는 $a_i$가 되므로

$e_i \leq e_{i+1}$ for $1 \leq i < j-n$

가 된다.

 

 

Time complexity