[정렬알고리즘] Bitonic Sort 바이토닉 정렬

대표적인 5가지 정렬 알고리즘을 직접 구현하고, 데이터 크기에 따른 성능을 비교하고 분석. 
알고리즘의 동작에 대한 분석 및 구현 코드의 설명.

Bitonic Sort _ 바이토닉 정렬

Conquer와 Combine을 거듭하며 bitonic sequence로 바꾼 후 정렬.
Bitonic Sequence 란, 증가했다 감소하거나 혹은 감소했다가 증가하는 시퀀스를 말한다. 0~1 Sequence라고 하며, 일반적으로 local maximum 혹은 local minimum 값으로 생각한다.

예를 들어, 010 101 01 10 0 1 모두 Bitonic Sequece 이다. 

Bitonic 정렬에서는 Bitonic Sequence를 1 0 혹은 0 1 서브 시퀀스를 2개 이하로 포함하는 시퀀스라한다. 

Bitonic Sort 알고리즘은 병렬 프로세서에서의 구현에 적합하게 만들어져 있는 알고리즘이다. 동작은 합병 정렬과 비슷하지만, 분할되고 합쳐지고 분할 되는 것이 반복되며, direction 값에 따른 Comparator가 동작되고, 별도로 저장할 저장공간이 필요 없다는 부분에서 다르다. Direction 은 오름차순, 혹은 내림차순을 결정하는 bool 값이다. 병렬 처리를 위해 sort 함수와 Merge 함수의 실행 및 비교할 때의 루프 등은 여러 스레드에서 병렬 적으로 수행되어야 한다. 

합병 정렬은 데이터를 반으로 나누어 각각 정렬을 시킨 후에 새로운 저장공간 S에 두 정렬의 값을 비교하며 앞에서부터 작은 값(혹은 큰 값)을 채워나가는 방식이다. Bitonic 정렬은 데이터를 계속 반으로 나누지만, Comparator에 따라서 정렬되고 합쳐진다. 비교할 때의 입력이 Bitonic Sequence 라면 두개의 Bitonic Sequence를 결과값으로 얻어낼 수 있다. 

 예제)

위의 예제 값으로 알 수 있듯이, Bitonic 소트는 반으로 계속 시퀀스를 나눈 후에 다시 합병시킬 때 정렬 방향( 오름차순, 혹은 내림 차순)에 따라서 합병 시키며 정렬한다. 이때 합병과정에서 Comparator를 거쳐 나오는 결과 데이터 시퀀스의 모양은 Bitonic Sequence이다. 

데이터 개수가 2^n 개 일 때 좋으며, 1024^2개가 넘어가면 GPU 에서의 처리하는 것이 더 빨라지게 된다. 

Parallel time 에서의 시간 복잡도는 최선의 경우 O(log^2(n)), 평균은 𝜃(log^2(n)), 최악의 경우에는 O(nlog^2(n)) 이 나온다. 

Bitonic Sort는 다른 저장공간이 필요하지 않기 때문에 in-place 이고, bitonic sequence 의 모양에 맞춰 정렬되기 때문에 unstable 한 정렬이다. 

Implementation

Swap 함수

모든 정렬 알고리즘에서 Swap 모듈을 사용하므로, 함수화 하여 사용한다. 

동적 배열의 주소 값과 정수 값 두개를 인자로 받고 첫번째 인자 a 와 두번째 인자 b를 index 로 하는 배열의 두 값을 바꿔주는 함수이다. 

void Swap(int* arr, int a, int b){
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
}

Bitonic Sort

Bitonic Sort 함수는 start 위치와 데이터 크기, 그리고 오름차순 혹은 내림 차순 정렬을 위한 bool 값을 인자로 받는다. Key 값을 계속 반으로 줄여가며 정렬을 수행한다. Bitonic Merge 함수에서 전체 재정렬 전에 반은 오름 차순, 반은 내림차순으로 정렬을 한다. 이는 정렬 후의 데이터를bitonic Sequence의 모양으로 만들기 위함이다. 

Bitonic Merge 함수는 인자로 start, 데이터 크기, bool 값을 받는다 이 값으로 입력 받은 데이터를 Comparator 비교기 함수를 통하여 두개의 Bitonic Sequence 로 만든다. 나눠진 이 Bitonic Sequence 는 다시 Merge 함수로 들어가 재 정렬 된다. 이렇게 분할되었다 합쳐졌다가 반복되면 최종적으로 정렬된 데이터가 나오게 된다. 

Comparator 비교기 함수는 bool 값에 따라 다르게 작동한다. 오름차순일때는 전>후 가 true 일 때  원소 둘의 자리를 바꿔주고, 내림차순일때는 전>후가 false 가 될 때 원소 둘의 자리를 바꿔준다. 

 

class BitonicSorter{
public:
	bool UP = true, DOWN = false; //오름차순, 내림차순 (for Bitonic Sort)

	void BitonicSort(int* arr, int start, int n, bool direction){ //start = 0, dir = 1
		if(n>1){ //comparator 가 비교할수있는 최소 데이터 갯수는 2개이다. 
			int k = n/2; //계속 반으로 줄여 나간다. 
			//Conquer 
			//comparator를 이요해 bitonic sequence를 만들기 위해 데이터를 반으로 나눈다. 
			BitonicSort(arr, start, k, UP); //반은 오름차순
			BitonicSort(arr, start+k, k, DOWN); //다음 반은 내림차순 
			//Combine
			BitonicMerge(arr, start, n, direction); //오름 차순 혹은 내림차순으로 전체 정렬을 수행한다. 
		}
	}
	void BitonicMerge(int* arr, int start, int n, bool direction){
		if(n>1){//comparator 가 비교할수있는 최소 데이터 갯수는 2개이다. 
			int k = n /2;
			//반으로 나눠진 데이터는 comparator을 지나 각각 bitonic sequence 를 가지게 된다.
			for(int i = start; i<start+k; i++) Comparator(arr, i, i+k, direction);
			//Conquer
			BitonicMerge(arr, start, k, direction); //반씩 나눠가며 재정렬
			BitonicMerge(arr, start+k, k, direction);//반씩 나눠가며 재정렬
			//Combine
		}
	}
	void Comparator(int* arr, int i , int j, bool direction){
		//dir 이 오름 차순일때, 내림차순일때에 따라 정렬한다. 
		//오름차순(1)일 때, 앞>뒤 true 이면 swap
		//내림차순(0)일 때, 앞>뒤 false 이면 swap
		if(direction == (arr[i] > arr[j])) Swap(arr, i, j);
	}
};
void Bitonic(int* arr, int n){ //Bitonic Sort
	BitonicSorter bs;
	steady_clock::time_point start, end; nanoseconds result;
	start = steady_clock::now();

	bs.BitonicSort(arr, 0, n, true); //오름 차순 정렬 ( true )

	end = steady_clock::now(); result = end - start;
	cout<<"4. Bitonic Sort                : "<<result.count()<<"ns"<<endl; //알고리즘 실행시간
}