1// parallel_sort.c
2// 병렬 병합 정렬 (Parallel Merge Sort)
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <pthread.h>
7#include <time.h>
8
9#define THRESHOLD 10000 // 이보다 작으면 단일 스레드
10
11typedef struct {
12 int* arr;
13 int left;
14 int right;
15} SortTask;
16
17// 병합
18void merge(int* arr, int left, int mid, int right) {
19 int n1 = mid - left + 1;
20 int n2 = right - mid;
21
22 int* L = malloc(n1 * sizeof(int));
23 int* R = malloc(n2 * sizeof(int));
24
25 memcpy(L, arr + left, n1 * sizeof(int));
26 memcpy(R, arr + mid + 1, n2 * sizeof(int));
27
28 int i = 0, j = 0, k = left;
29 while (i < n1 && j < n2) {
30 arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
31 }
32 while (i < n1) arr[k++] = L[i++];
33 while (j < n2) arr[k++] = R[j++];
34
35 free(L);
36 free(R);
37}
38
39// 단일 스레드 병합 정렬
40void merge_sort_single(int* arr, int left, int right) {
41 if (left < right) {
42 int mid = left + (right - left) / 2;
43 merge_sort_single(arr, left, mid);
44 merge_sort_single(arr, mid + 1, right);
45 merge(arr, left, mid, right);
46 }
47}
48
49// 멀티스레드 병합 정렬
50void* merge_sort_parallel(void* arg) {
51 SortTask* task = (SortTask*)arg;
52 int* arr = task->arr;
53 int left = task->left;
54 int right = task->right;
55
56 if (left >= right) return NULL;
57
58 // 작은 배열은 단일 스레드로
59 if (right - left < THRESHOLD) {
60 merge_sort_single(arr, left, right);
61 return NULL;
62 }
63
64 int mid = left + (right - left) / 2;
65
66 // 왼쪽 절반: 새 스레드
67 SortTask left_task = { arr, left, mid };
68 pthread_t left_thread;
69 pthread_create(&left_thread, NULL, merge_sort_parallel, &left_task);
70
71 // 오른쪽 절반: 현재 스레드
72 SortTask right_task = { arr, mid + 1, right };
73 merge_sort_parallel(&right_task);
74
75 // 왼쪽 스레드 대기
76 pthread_join(left_thread, NULL);
77
78 // 병합
79 merge(arr, left, mid, right);
80
81 return NULL;
82}
83
84// 배열 출력
85void print_array(int* arr, int n) {
86 for (int i = 0; i < n && i < 20; i++) {
87 printf("%d ", arr[i]);
88 }
89 if (n > 20) printf("...");
90 printf("\n");
91}
92
93// 배열 검증
94int is_sorted(int* arr, int n) {
95 for (int i = 1; i < n; i++) {
96 if (arr[i] < arr[i - 1]) return 0;
97 }
98 return 1;
99}
100
101int main(void) {
102 srand(time(NULL));
103
104 int n = 1000000; // 백만 개
105 int* arr1 = malloc(n * sizeof(int));
106 int* arr2 = malloc(n * sizeof(int));
107
108 // 랜덤 배열 생성
109 for (int i = 0; i < n; i++) {
110 arr1[i] = rand();
111 arr2[i] = arr1[i]; // 복사
112 }
113
114 printf("배열 크기: %d\n\n", n);
115
116 // 단일 스레드 정렬
117 clock_t start = clock();
118 merge_sort_single(arr1, 0, n - 1);
119 clock_t end = clock();
120 double single_time = (double)(end - start) / CLOCKS_PER_SEC;
121
122 printf("단일 스레드: %.3f초\n", single_time);
123 printf("정렬 검증: %s\n\n", is_sorted(arr1, n) ? "OK" : "FAIL");
124
125 // 멀티스레드 정렬
126 start = clock();
127 SortTask task = { arr2, 0, n - 1 };
128 merge_sort_parallel(&task);
129 end = clock();
130 double parallel_time = (double)(end - start) / CLOCKS_PER_SEC;
131
132 printf("멀티스레드: %.3f초\n", parallel_time);
133 printf("정렬 검증: %s\n\n", is_sorted(arr2, n) ? "OK" : "FAIL");
134
135 printf("속도 향상: %.2fx\n", single_time / parallel_time);
136
137 free(arr1);
138 free(arr2);
139
140 return 0;
141}