1/*
2 * 정렬 알고리즘 (Sorting Algorithms)
3 * Bubble, Selection, Insertion, Merge, Quick, Heap, Counting, Radix
4 *
5 * 다양한 정렬 알고리즘의 구현과 비교입니다.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11
12/* =============================================================================
13 * 1. 버블 정렬 - O(n²)
14 * ============================================================================= */
15
16void bubble_sort(int arr[], int n) {
17 for (int i = 0; i < n - 1; i++) {
18 int swapped = 0;
19 for (int j = 0; j < n - i - 1; j++) {
20 if (arr[j] > arr[j + 1]) {
21 int temp = arr[j];
22 arr[j] = arr[j + 1];
23 arr[j + 1] = temp;
24 swapped = 1;
25 }
26 }
27 if (!swapped) break; /* 최적화: 이미 정렬됨 */
28 }
29}
30
31/* =============================================================================
32 * 2. 선택 정렬 - O(n²)
33 * ============================================================================= */
34
35void selection_sort(int arr[], int n) {
36 for (int i = 0; i < n - 1; i++) {
37 int min_idx = i;
38 for (int j = i + 1; j < n; j++) {
39 if (arr[j] < arr[min_idx]) {
40 min_idx = j;
41 }
42 }
43 if (min_idx != i) {
44 int temp = arr[i];
45 arr[i] = arr[min_idx];
46 arr[min_idx] = temp;
47 }
48 }
49}
50
51/* =============================================================================
52 * 3. 삽입 정렬 - O(n²)
53 * ============================================================================= */
54
55void insertion_sort(int arr[], int n) {
56 for (int i = 1; i < n; i++) {
57 int key = arr[i];
58 int j = i - 1;
59
60 while (j >= 0 && arr[j] > key) {
61 arr[j + 1] = arr[j];
62 j--;
63 }
64 arr[j + 1] = key;
65 }
66}
67
68/* =============================================================================
69 * 4. 병합 정렬 - O(n log n)
70 * ============================================================================= */
71
72void merge(int arr[], int left, int mid, int right) {
73 int n1 = mid - left + 1;
74 int n2 = right - mid;
75
76 int* L = malloc(n1 * sizeof(int));
77 int* R = malloc(n2 * sizeof(int));
78
79 for (int i = 0; i < n1; i++)
80 L[i] = arr[left + i];
81 for (int j = 0; j < n2; j++)
82 R[j] = arr[mid + 1 + j];
83
84 int i = 0, j = 0, k = left;
85
86 while (i < n1 && j < n2) {
87 if (L[i] <= R[j]) {
88 arr[k++] = L[i++];
89 } else {
90 arr[k++] = R[j++];
91 }
92 }
93
94 while (i < n1)
95 arr[k++] = L[i++];
96 while (j < n2)
97 arr[k++] = R[j++];
98
99 free(L);
100 free(R);
101}
102
103void merge_sort(int arr[], int left, int right) {
104 if (left < right) {
105 int mid = left + (right - left) / 2;
106 merge_sort(arr, left, mid);
107 merge_sort(arr, mid + 1, right);
108 merge(arr, left, mid, right);
109 }
110}
111
112/* =============================================================================
113 * 5. 퀵 정렬 - O(n log n) 평균
114 * ============================================================================= */
115
116int partition(int arr[], int low, int high) {
117 int pivot = arr[high];
118 int i = low - 1;
119
120 for (int j = low; j < high; j++) {
121 if (arr[j] < pivot) {
122 i++;
123 int temp = arr[i];
124 arr[i] = arr[j];
125 arr[j] = temp;
126 }
127 }
128
129 int temp = arr[i + 1];
130 arr[i + 1] = arr[high];
131 arr[high] = temp;
132
133 return i + 1;
134}
135
136void quick_sort(int arr[], int low, int high) {
137 if (low < high) {
138 int pi = partition(arr, low, high);
139 quick_sort(arr, low, pi - 1);
140 quick_sort(arr, pi + 1, high);
141 }
142}
143
144/* 3중 피벗 퀵소트 */
145int partition_median(int arr[], int low, int high) {
146 int mid = low + (high - low) / 2;
147
148 /* 3개 값 정렬 */
149 if (arr[low] > arr[mid]) {
150 int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
151 }
152 if (arr[mid] > arr[high]) {
153 int t = arr[mid]; arr[mid] = arr[high]; arr[high] = t;
154 }
155 if (arr[low] > arr[mid]) {
156 int t = arr[low]; arr[low] = arr[mid]; arr[mid] = t;
157 }
158
159 /* 중앙값을 high-1 위치로 */
160 int t = arr[mid]; arr[mid] = arr[high - 1]; arr[high - 1] = t;
161
162 return partition(arr, low, high);
163}
164
165/* =============================================================================
166 * 6. 힙 정렬 - O(n log n)
167 * ============================================================================= */
168
169void heapify(int arr[], int n, int i) {
170 int largest = i;
171 int left = 2 * i + 1;
172 int right = 2 * i + 2;
173
174 if (left < n && arr[left] > arr[largest])
175 largest = left;
176
177 if (right < n && arr[right] > arr[largest])
178 largest = right;
179
180 if (largest != i) {
181 int temp = arr[i];
182 arr[i] = arr[largest];
183 arr[largest] = temp;
184 heapify(arr, n, largest);
185 }
186}
187
188void heap_sort(int arr[], int n) {
189 /* 최대 힙 구성 */
190 for (int i = n / 2 - 1; i >= 0; i--) {
191 heapify(arr, n, i);
192 }
193
194 /* 정렬 */
195 for (int i = n - 1; i > 0; i--) {
196 int temp = arr[0];
197 arr[0] = arr[i];
198 arr[i] = temp;
199 heapify(arr, i, 0);
200 }
201}
202
203/* =============================================================================
204 * 7. 계수 정렬 - O(n + k)
205 * ============================================================================= */
206
207void counting_sort(int arr[], int n, int max_val) {
208 int* count = calloc(max_val + 1, sizeof(int));
209 int* output = malloc(n * sizeof(int));
210
211 /* 빈도 계산 */
212 for (int i = 0; i < n; i++) {
213 count[arr[i]]++;
214 }
215
216 /* 누적 합 */
217 for (int i = 1; i <= max_val; i++) {
218 count[i] += count[i - 1];
219 }
220
221 /* 출력 배열 생성 (안정 정렬) */
222 for (int i = n - 1; i >= 0; i--) {
223 output[count[arr[i]] - 1] = arr[i];
224 count[arr[i]]--;
225 }
226
227 /* 결과 복사 */
228 for (int i = 0; i < n; i++) {
229 arr[i] = output[i];
230 }
231
232 free(count);
233 free(output);
234}
235
236/* =============================================================================
237 * 8. 기수 정렬 - O(d * (n + k))
238 * ============================================================================= */
239
240int get_max(int arr[], int n) {
241 int max = arr[0];
242 for (int i = 1; i < n; i++) {
243 if (arr[i] > max) max = arr[i];
244 }
245 return max;
246}
247
248void counting_sort_exp(int arr[], int n, int exp) {
249 int* output = malloc(n * sizeof(int));
250 int count[10] = {0};
251
252 for (int i = 0; i < n; i++) {
253 count[(arr[i] / exp) % 10]++;
254 }
255
256 for (int i = 1; i < 10; i++) {
257 count[i] += count[i - 1];
258 }
259
260 for (int i = n - 1; i >= 0; i--) {
261 output[count[(arr[i] / exp) % 10] - 1] = arr[i];
262 count[(arr[i] / exp) % 10]--;
263 }
264
265 for (int i = 0; i < n; i++) {
266 arr[i] = output[i];
267 }
268
269 free(output);
270}
271
272void radix_sort(int arr[], int n) {
273 int max = get_max(arr, n);
274
275 for (int exp = 1; max / exp > 0; exp *= 10) {
276 counting_sort_exp(arr, n, exp);
277 }
278}
279
280/* =============================================================================
281 * 테스트
282 * ============================================================================= */
283
284void print_array(int arr[], int n) {
285 printf("[");
286 for (int i = 0; i < n; i++) {
287 printf("%d", arr[i]);
288 if (i < n - 1) printf(", ");
289 }
290 printf("]\n");
291}
292
293void copy_array(int src[], int dst[], int n) {
294 for (int i = 0; i < n; i++) {
295 dst[i] = src[i];
296 }
297}
298
299int main(void) {
300 printf("============================================================\n");
301 printf("정렬 알고리즘 (Sorting Algorithms) 예제\n");
302 printf("============================================================\n");
303
304 int original[] = {64, 34, 25, 12, 22, 11, 90, 45};
305 int n = 8;
306 int arr[8];
307
308 /* 1. 버블 정렬 */
309 printf("\n[1] 버블 정렬 - O(n²)\n");
310 copy_array(original, arr, n);
311 printf(" 정렬 전: ");
312 print_array(arr, n);
313 bubble_sort(arr, n);
314 printf(" 정렬 후: ");
315 print_array(arr, n);
316
317 /* 2. 선택 정렬 */
318 printf("\n[2] 선택 정렬 - O(n²)\n");
319 copy_array(original, arr, n);
320 selection_sort(arr, n);
321 printf(" 결과: ");
322 print_array(arr, n);
323
324 /* 3. 삽입 정렬 */
325 printf("\n[3] 삽입 정렬 - O(n²)\n");
326 copy_array(original, arr, n);
327 insertion_sort(arr, n);
328 printf(" 결과: ");
329 print_array(arr, n);
330
331 /* 4. 병합 정렬 */
332 printf("\n[4] 병합 정렬 - O(n log n)\n");
333 copy_array(original, arr, n);
334 merge_sort(arr, 0, n - 1);
335 printf(" 결과: ");
336 print_array(arr, n);
337
338 /* 5. 퀵 정렬 */
339 printf("\n[5] 퀵 정렬 - O(n log n) 평균\n");
340 copy_array(original, arr, n);
341 quick_sort(arr, 0, n - 1);
342 printf(" 결과: ");
343 print_array(arr, n);
344
345 /* 6. 힙 정렬 */
346 printf("\n[6] 힙 정렬 - O(n log n)\n");
347 copy_array(original, arr, n);
348 heap_sort(arr, n);
349 printf(" 결과: ");
350 print_array(arr, n);
351
352 /* 7. 계수 정렬 */
353 printf("\n[7] 계수 정렬 - O(n + k)\n");
354 int arr7[] = {4, 2, 2, 8, 3, 3, 1};
355 printf(" 정렬 전: ");
356 print_array(arr7, 7);
357 counting_sort(arr7, 7, 8);
358 printf(" 정렬 후: ");
359 print_array(arr7, 7);
360
361 /* 8. 기수 정렬 */
362 printf("\n[8] 기수 정렬 - O(d * n)\n");
363 int arr8[] = {170, 45, 75, 90, 802, 24, 2, 66};
364 printf(" 정렬 전: ");
365 print_array(arr8, 8);
366 radix_sort(arr8, 8);
367 printf(" 정렬 후: ");
368 print_array(arr8, 8);
369
370 /* 9. 알고리즘 비교 */
371 printf("\n[9] 정렬 알고리즘 비교\n");
372 printf(" | 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 |\n");
373 printf(" |----------|----------|----------|----------|-------|------|\n");
374 printf(" | 버블 | O(n) | O(n²) | O(n²) | O(1) | Yes |\n");
375 printf(" | 선택 | O(n²) | O(n²) | O(n²) | O(1) | No |\n");
376 printf(" | 삽입 | O(n) | O(n²) | O(n²) | O(1) | Yes |\n");
377 printf(" | 병합 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Yes |\n");
378 printf(" | 퀵 | O(nlogn) | O(nlogn) | O(n²) | O(logn)| No |\n");
379 printf(" | 힙 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | No |\n");
380 printf(" | 계수 | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes |\n");
381 printf(" | 기수 | O(dn) | O(dn) | O(dn) | O(n+k)| Yes |\n");
382
383 printf("\n============================================================\n");
384
385 return 0;
386}