정렬되지 않은 정수 배열이 주어졌을 때, 멀티스레딩(Multi-threading)으로 구현한 병합 정렬 기법을 사용해 배열을 정렬하는 것이 이 글의 목표입니다.
병합 정렬(Merge Sort)이란?
병합 정렬은 분할 정복(Divide and Conquer) 기법에 기반한 정렬 알고리즘입니다. 배열을 절반씩 계속 나눈 후, 정렬된 상태로 다시 결합하는 방식으로 동작합니다.
병합 정렬 알고리즘
리스트에 원소가 하나뿐이라면 해당 원소를 그대로 반환합니다.
그렇지 않다면, 더 이상 나눌 수 없을 때까지 데이터를 재귀적으로 두 부분으로 분할합니다.
마지막으로, 작은 리스트들을 정렬된 순서로 병합하여 새로운 리스트를 만듭니다.
멀티스레딩(Multi-threading)
운영체제에서 스레드(Thread)는 작업의 일부를 실행하는 역할을 담당하는 경량 프로세스입니다. 스레드들은 공통 자원을 공유하면서 작업을 동시에(concurrently) 수행할 수 있습니다.
멀티스레딩은 하나의 프로세서 위에서 여러 스레드를 실행하여 작업을 동시에 처리하는 멀티태스킹의 한 구현 방식입니다. 하나의 응용 프로그램 내부의 특정 연산을 개별 스레드로 세분화하며, 각 스레드는 서로 병렬(parallel)로 실행될 수 있습니다.
입출력 예시
입력 − int arr[] = {3, 2, 1, 10, 8, 5, 7, 9, 4}
출력 − 정렬된 배열: 1, 2, 3, 4, 5, 7, 8, 9, 10
설명 − 정수 값으로 이루어진 정렬되지 않은 배열이 주어지며, 멀티스레딩을 활용한 병합 정렬로 이를 정렬합니다.
입력 − int arr[] = {5, 3, 1, 45, 32, 21, 50}
출력 − 정렬된 배열: 1, 3, 5, 21, 32, 45, 50
설명 − 마찬가지로 정렬되지 않은 정수 배열을 멀티스레딩 기반 병합 정렬로 정렬합니다.
프로그램 구현 접근 방식
C++ STL의 rand() 메서드를 사용해 난수를 생성하는 것부터 시작합니다.
pthread_t 타입의 배열 P_TH[thread_size]를 생성합니다.
i가 0부터 스레드 크기보다 작을 때까지 반복문을 수행하면서, pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL) 메서드를 호출해 주어진 배열 값을 대상으로 스레드를 생성합니다.
combine_array(0, (size / 2 - 1) / 2, size / 2 - 1), combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1), combine_array(0, (size - 1)/2, size - 1) 함수를 차례로 호출합니다.
정수형 배열 arr[]에 저장된 정렬 결과를 출력합니다.
void* Sorting_Threading(void* arg) 함수 내부에서는 다음을 수행합니다.
set_val 변수를 temp_val++ 값으로 선언하고, first를 set_val * (size / 4)로, end를 (set_val + 1) * (size / 4) - 1로, mid_val을 first + (end - first) / 2로 설정합니다.
first가 end보다 작은 경우 Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end)를 재귀 호출한 뒤 combine_array(first, mid_val, end)를 호출합니다.
void Sorting_Threading(int first, int end) 함수 내부에서는 다음을 수행합니다.
mid_val을 first + (end - first) / 2로 선언합니다.
first가 end보다 작으면 Sorting_Threading(first, mid_val), Sorting_Threading(mid_val + 1, end)를 재귀 호출하고 combine_array(first, mid_val, end)를 호출합니다.
void combine_array(int first, int mid_val, int end) 함수 내부에서는 다음을 수행합니다.
int* start = new int[mid_val - first + 1], int* last = new int[end - mid_val], temp_1 = mid_val - first + 1, temp_2 = end - mid_val, i, j, k = first 변수를 선언합니다.
i가 0부터 temp_1보다 작을 때까지 반복하며 start[i]에 arr[i + first]를 대입합니다.
i가 0부터 temp_2보다 작을 때까지 반복하며 last[i]에 arr[i + mid_val + 1]을 대입합니다.
i와 j를 0으로 설정합니다. i가 temp_1보다 작고 j가 temp_2보다 작은 동안 while 문을 수행하며, start[i]가 last[j]보다 작거나 같으면 arr[k++]에 start[i++]를 대입하고, 그렇지 않으면 arr[k++]에 last[j++]를 대입합니다.
i가 temp_1보다 작은 동안 arr[k++] = start[i++]를 수행하고, j가 temp_2보다 작은 동안 arr[k++] = last[j++]를 수행하여 남은 원소를 채웁니다.
예제 코드
#include <iostream>
#include <pthread.h>
#include <time.h>
#define size 20
#define thread_size 4
using namespace std;
int arr[size];
int temp_val = 0;
void combine_array(int first, int mid_val, int end){
int* start = new int[mid_val - first + 1];
int* last = new int[end - mid_val];
int temp_1 = mid_val - first + 1;
int temp_2 = end - mid_val;
int i, j;
int k = first;
for(i = 0; i < temp_1; i++){
start[i] = arr[i + first];
}
for (i = 0; i < temp_2; i++){
last[i] = arr[i + mid_val + 1];
}
i = j = 0;
while(i < temp_1 && j < temp_2){
if(start[i] <= last[j]){
arr[k++] = start[i++];
}
else{
arr[k++] = last[j++];
}
}
while (i < temp_1){
arr[k++] = start[i++];
}
while (j < temp_2){
arr[k++] = last[j++];
}
}
void Sorting_Threading(int first, int end){
int mid_val = first + (end - first) / 2;
if(first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
void* Sorting_Threading(void* arg){
int set_val = temp_val++;
int first = set_val * (size / 4);
int end = (set_val + 1) * (size / 4) - 1;
int mid_val = first + (end - first) / 2;
if (first < end){
Sorting_Threading(first, mid_val);
Sorting_Threading(mid_val + 1, end);
combine_array(first, mid_val, end);
}
}
int main(){
for(int i = 0; i < size; i++){
arr[i] = rand() % 100;
}
pthread_t P_TH[thread_size];
for(int i = 0; i < thread_size; i++){
pthread_create(&P_TH[i], NULL, Sorting_Threading, (void*)NULL);
}
for(int i = 0; i < 4; i++){
pthread_join(P_TH[i], NULL);
}
combine_array(0, (size / 2 - 1) / 2, size / 2 - 1);
combine_array(size / 2, size/2 + (size-1-size/2)/2, size - 1);
combine_array(0, (size - 1)/2, size - 1);
cout<<"Merge Sort using Multi-threading: ";
for (int i = 0; i < size; i++){
cout << arr[i] << " ";
}
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Merge Sort using Multi-threading: 15 21 26 26 27 35 36 40 49 59 62 63 72 77 83 86 86 90 92 93