바이토닉 정렬(Bitonic Sort)은 최적의 구현을 목표로 설계된 병렬 정렬 알고리즘으로, 하드웨어 및 병렬 프로세서 배열과 함께 사용할 때 가장 뛰어난 성능을 발휘합니다.
병합 정렬(merge sort)에 비해 단독 실행 시 효율성은 떨어지지만, 병렬 구현에는 매우 적합합니다. 그 이유는 비교 순서가 사전에 정의되어 있어 각 비교 연산이 정렬 대상 데이터와 독립적으로 수행될 수 있기 때문입니다.
바이토닉 정렬이 효과적으로 작동하려면 정렬할 요소의 개수가 반드시 2^n 형태, 즉 2의 거듭제곱이어야 한다는 점에 유의해야 합니다.
바이토닉 수열(Bitonic Sequence)이란?
바이토닉 정렬의 핵심 개념은 바이토닉 수열입니다. 이는 요소의 값이 먼저 증가했다가 이후 감소하는 수열을 의미합니다.
배열 arr[0 … (n-1)]에서 인덱스 i(0 ≤ i ≤ n-1)가 존재하여 arr[i]가 배열 전체에서 최댓값이라면, 해당 배열은 바이토닉 수열입니다. 즉, 다음 조건을 만족합니다.
arr[0] <= arr[1] … <= arr[i] 그리고 arr[i] >= arr[i+1] … >= arr[n-1]
바이토닉 수열의 특수한 성질
바이토닉 수열은 회전(rotation)해도 여전히 바이토닉 수열입니다.
요소가 증가 후 감소하는 순서로 배치된 수열은 모두 바이토닉 수열입니다.
바이토닉 수열 만들기
바이토닉 수열을 생성하려면 두 개의 부분 수열을 만듭니다. 하나는 오름차순으로, 다른 하나는 내림차순으로 구성합니다.
예를 들어 다음 수열을 바이토닉 수열로 변환해 보겠습니다.
arr[] = {3, 4, 1, 9, 2, 7, 5, 6}먼저 요소들을 쌍(pair)으로 묶은 뒤, 한 쌍은 오름차순, 다음 쌍은 내림차순이 되도록 번갈아 배치합니다.
arr[] = {(3, 4), (1, 9), (2, 7), (5, 6)}
// 바이토닉 수열 쌍 생성…
arr[] = {(3, 4), (9, 1), (2, 7), (6, 5)}그다음, 이 쌍들을 다시 묶어 4개 요소짜리 바이토닉 수열을 만들고, 거리가 2만큼 떨어진 요소들(즉, i번째와 i+2번째)을 서로 비교합니다.
arr[] = {(3, 4, 9, 1), (2, 7, 6, 5)}첫 번째 집합은 오름차순 바이토닉 수열로 변환합니다.
(3, 4, 9, 1) : 거리가 2인 요소들 비교 (3, 1, 9, 4) : 이제 인접한 요소들 확인 (1, 3, 4, 9) → 오름차순 바이토닉 수열 완성
두 번째 집합은 내림차순 바이토닉 수열로 변환합니다.
(2, 7, 6, 5) : 거리가 2인 요소들 비교 (6, 7, 2, 5) : 이제 인접한 요소들 확인 (7, 6, 5, 2) → 내림차순 바이토닉 수열 완성
최종적으로 크기 8의 바이토닉 수열을 얻게 됩니다.
1, 3, 4, 9, 7, 6, 5, 2
이제 바이토닉 수열의 개념을 익혔으므로, 실제 바이토닉 정렬 과정을 살펴보겠습니다.
바이토닉 정렬의 동작 단계
바이토닉 수열을 정렬하기 위해서는 다음 단계를 따릅니다.
1단계 — 바이토닉 수열을 생성합니다.
2단계 — 절반은 오름차순, 나머지 절반은 내림차순으로 구성된 바이토닉 수열이 준비됩니다.
3단계 — 두 절반의 첫 번째 요소들을 서로 비교하고 필요하면 교환(swap)합니다. 이어서 두 번째, 세 번째, 네 번째 요소들도 같은 방식으로 처리합니다.
4단계 — 수열에서 두 칸씩 떨어진 요소들을 비교하고 교환합니다.
5단계 — 마지막으로 수열의 인접한 요소들을 비교하고 교환합니다.
6단계 — 모든 교환이 완료되면 정렬된 배열을 얻습니다.
C++ 구현 예제
다음은 바이토닉 정렬을 구현한 C++ 프로그램입니다.
#include<iostream>
using namespace std;
void bitonicSeqMerge(int a[], int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
for (int i=start; i<start+k; i++)
if (direction==(a[i]>a[i+k]))
swap(a[i],a[i+k]);
bitonicSeqMerge(a, start, k, direction);
bitonicSeqMerge(a, start+k, k, direction);
}
}
void bitonicSortrec(int a[],int start, int BseqSize, int direction) {
if (BseqSize>1){
int k = BseqSize/2;
bitonicSortrec(a, start, k, 1);
bitonicSortrec(a, start+k, k, 0);
bitonicSeqMerge(a,start, BseqSize, direction);
}
}
void bitonicSort(int a[], int size, int up) {
bitonicSortrec(a, 0, size, up);
}
int main() {
int a[]= {5, 10, 51, 8, 1, 9, 6, 22};
int size = sizeof(a)/sizeof(a[0]);
printf("원본 배열: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
bitonicSort(a, size, 1);
printf("\n정렬된 배열: \n");
for (int i=0; i<size; i++)
printf("%d\t", a[i]);
return 0;
}실행 결과
원본 배열: 5 10 51 8 1 9 6 22 정렬된 배열: 1 5 6 8 9 10 22 51