Bitonic Sort in Distributed Parallel Computer System

Bitonic Sort

  기본적으로 Bitonic Sort는 Bitonic Sequence에서만 사용할 수 있다. 하지만 편법을 적용하면 일반적인 Sequence에 대해서도 Bitonic Sort를 시킬 수 있다. 이 글에서는 Bitonic Sequence에 대한 Sort는 이미 알고리즘을 알고 있다고 가정하고, 일반적인 수열에 대해서의 Bitonic Sort에 대해 알아볼 것이다. Bitonic Sequence에서의 Bitonic Sort는 O(log n)으로 구해진다.

  다음과 같이 무질서한 수열이 있다고 해보자.

4 9 7 3 5 8 1 6

  어떤 규칙도 보이지 않는 수열이다. 이것을 Bitonic으로 만들어 정렬할 것이다. 이 수열에 대한 것만 아니라 일반적인 관점에서 보아야 하는 것이 포인트다. 가장 작은 단위부터 거슬러 올라가면 쉽게 Bitonic Sort 할 수 있다.

1. 2개씩 짝지었을 때 Bitonic으로 만들기

4 9 / 7 3 / 5 8 / 1 6

  두 개씩 짝지었을때는 무조건 Bitonic일 수밖에 없다. 두 개의 숫자가 있다면 이것의 정렬은 쭉 커지거나 쭉 작아지는 두가지 경우밖에 존재하지 않는다.

2. 4개씩 짝지었을 때 Bitonic으로 만들기

  간단한 아이디어이다. 한 개의 짝은 커지게하고, 다른 한 개의 짝은 작아지게 하면 무조건 커졌다가 작아지는 Bitonic이 될 수밖에 없다. 즉, 1)번의 수열에서 홀수 번째의 수열은 커지는 순으로 두고, 짝수 번째의 수열은 작아지는 순으로 배열한 뒤 합치면 Bitonic이 될 것이다.

Step 1) 홀수번째 수열: 증가, 짝수번째 수열: 감소 순으로 배열

4 9 / 7 3 / 5 8 / 6 1

Step 2) 합치면 Bitonic

4 9 7 3 / 5 8 6 1

3. 8개씩 짝지었을 때 Bitonic으로 만들기

  이번에는 2번 과정에서 쓰이지 않았던 과정이 추가된다. 2번에 대해서 Bitonic Sort를 해주어야 한다. 이제 이 단계부터 본격적으로 Bitonic Sorting을 해야 하고 이 Sorting과정에서의 Time Complexity는 O(log n) 이다.

3 4 7 9 / 1 5 6 8

  그리고 2)에서 했던 것과 같은 요령으로 홀수 번째 수열은 증가하는 순서대로, 짝수 번째 수열은 감소하는 순서대로 둔다.

Step 1) 홀수 번째 수열: 증가, 짝수 번째 수열: 감소

3 4 7 9 / 8 6 5 1

Step 2) 합치면 Bitonic

3 4 7 9 8 6 5 1

4. 최종 Bitonic Sort

  3)에서 나온 수열은 Bitonic이므로 Bitonic Sort 시킬 수 있고, 시키면 이제 정렬이 완료된다.

1 3 4 5 6 7 8 9

  Overall Time complexity는 총 단계가 log n개 이고, 또한 각 단계마다 Bitonic Sort를 시키므로 Bitonic Sort의 Running Time인 O(log n)을 곱하면 구할 수 있다. 즉, 결과는 O(log² n)이 나온다.

  아래 표는 다른 예제이다.