비토닉 정렬(Bitonic Sort)은 정렬할 데이터에 따라 비교 순서가 달라지는 것이 아니라, 미리 정의된 시퀀스(비토닉 시퀀스)를 기준으로 비교가 이루어지는 정렬 알고리즘입니다. 여기서 비토닉 시퀀스란 먼저 증가하다가 이후 감소하는(또는 그 반대의) 형태를 가진 수열을 의미합니다.
이러한 특성 덕분에 비토닉 정렬은 비교 경로가 고정되어 있어 병렬 처리 환경에서 특히 효율적이며, GPU 연산이나 하드웨어 가속이 필요한 분야에서 널리 활용됩니다. 아래에서 자바로 구현한 비토닉 정렬 예제를 살펴보겠습니다.
예제 코드
public class Demo{
void compare_swap(int my_arr[], int i, int j, int direction){
if ((my_arr[i] > my_arr[j] && direction == 1) || (my_arr[i] < my_arr[j] && direction == 0)){
int temp = my_arr[i];
my_arr[i] = my_arr[j];
my_arr[j] = temp;
}
}
void merge_vals(int my_arr[], int low, int cnt, int direction){
if (cnt>1){
int k = cnt/2;
for (int i=low; i<low+k; i++)
compare_swap(my_arr,i, i+k, direction);
merge_vals(my_arr,low, k, direction);
merge_vals(my_arr,low+k, k, direction);
}
}
void sort_vals(int my_arr[], int low, int cnt, int direction){
if (cnt>1){
int k = cnt/2;
sort_vals(my_arr, low, k, 1);
sort_vals(my_arr,low+k, k, 0);
merge_vals(my_arr, low, cnt, direction);
}
}
static void print_vals(int my_arr[]){
int n = my_arr.length;
for (int i=0; i<n; ++i)
System.out.print(my_arr[i] + " ");
System.out.println();
}
public static void main(String args[]){
int my_arr[] = {12, 67, 91, 54, 72, 32, 11, 0};
int up = 1;
Demo my_ob = new Demo();
System.out.println("The object of the class has been created.");
my_ob.sort_vals(my_arr, 0, my_arr.length, up);
System.out.println("The array after performing bitonic sort is");
print_vals(my_arr);
}
}실행 결과
The object of the class has been created. The array after performing bitonic sort is 0 11 12 32 54 67 72 91
코드 상세 설명
1. compare_swap 함수
이름이 Demo인 클래스에는 compare_swap 함수가 정의되어 있습니다. 이 함수는 배열과 두 개의 인덱스(i, j), 그리고 정렬 방향(direction)을 매개변수로 받습니다. 지정된 방향에 따라 두 요소의 크기를 비교한 뒤, 정렬 조건에 맞지 않으면 두 요소의 자리를 서로 교환(swap)합니다.
2. merge_vals 함수
merge_vals 함수는 배열을 순회하면서 일정한 간격(k)만큼 떨어져 있는 요소들끼리 compare_swap 함수를 호출합니다. 이후 재귀적으로 자기 자신을 호출하여 분할된 부분 배열들을 하나의 정렬된 시퀀스로 병합합니다.
3. sort_vals 함수
sort_vals 함수는 배열을 절반으로 나누어, 앞쪽 절반은 오름차순(방향 값 1), 뒤쪽 절반은 내림차순(방향 값 0)으로 각각 정렬합니다. 이렇게 만들어진 비토닉 시퀀스를 merge_vals 함수에 전달하여 최종적으로 하나의 완전히 정렬된 배열로 합치는 역할을 담당합니다.
4. print_vals 함수
static으로 선언된 print_vals 함수는 배열을 매개변수로 받아, for 루프를 통해 배열의 모든 요소를 순회하면서 콘솔에 차례대로 출력합니다.
5. main 함수
main 함수에서는 정렬할 배열과 오름차순을 의미하는 'up' 변수(값 1)를 정의합니다. 이후 Demo 클래스의 객체를 생성하고, 해당 객체의 sort_vals 함수를 호출하여 배열 전체에 대해 비토닉 정렬을 수행합니다. 마지막으로 정렬이 완료된 배열을 print_vals 함수를 통해 콘솔에 출력합니다.
마무리
위 예제처럼 비토닉 정렬은 분할-정복(divide and conquer) 방식으로 동작하며, 입력 크기가 2의 거듭제곱일 때 가장 효율적으로 작동합니다. 비교 순서가 데이터와 무관하게 고정되어 있다는 점은 일반적인 퀵 정렬이나 병합 정렬과 차별화되는 핵심 특징이며, 이 덕분에 병렬 컴퓨팅 환경에서 강력한 성능을 발휘합니다.