Page 249 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

31 printf("a[%d] : ", i);
32 scanf("%d", &a[i]);
33 } while(a[i] < a[i - 1]);
34 }
35 printf("b[0] : ");
36 scanf("%d", &b[0]);
37 for(i = 1; i < nb; i++) {
38 do {
39 printf("b[%d] : ", i);
40 scanf("%d", &b[i]);
41 } while(b[i] < b[i - 1]);
42 }
43
44 /* 배열 a와 b를 병합하여 c에 저장 */
45 merge(a, na, b, nb, c);
46 puts("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
47 for(i = 0; i < na + nb; i++)
48 printf("c[%2d] = %2d\n", i, c[i]);
49 free(a); free(b); free(c);
50
51 return 0;
52 }

실습 6-13은 3개의 반복문을 늘어놓는 단순한 알고리즘으로 구현되어 있습니다. 병합에 필
요한 시간 복잡도는 O(n)입니다.

병합 정렬

정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬
(merge sort)이라고 합니다. 그림 6-29는 병합 정렬을 간단히 나타낸 것으로, 먼저 배열을 앞
부분과 뒷부분으로 나눕니다. 이 그림은 배열의 요소 개수가 12개이므로 6개의 배열로 각각

나눕니다. 나눈 두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬할 수 있습니다.

06•정렬 249