C 프로그래밍에서 배열 병합(Merge)이란 두 개의 배열을 입력받아 하나로 합치고, 그 결과를 세 번째 배열에 저장하는 작업을 의미합니다. 특히 각 배열이 정렬되어 있다면, 두 배열의 요소를 순서대로 비교하면서 효율적으로 병합할 수 있습니다. 이 글에서는 병합 알고리즘의 핵심 로직과 전체 예제 코드, 실행 결과까지 자세히 살펴보겠습니다.
두 배열을 병합하는 핵심 로직
병합 알고리즘의 기본 아이디어는 간단합니다. 각 배열을 가리키는 인덱스 변수(j, k)를 두고, 두 배열의 현재 요소를 비교한 뒤 더 작은 값을 결과 배열(c)에 차례대로 저장하는 방식입니다.
J=0,k=0
for(i=0;i<o;i++) { // 두 배열 병합
if(a[j]<=b[k]){
c[i]=a[j];
j++;
} else {
c[i]=b[k];
k++;
}
}동작 원리 단계별 이해
- 배열 a와 배열 b의 첫 번째 요소부터 비교를 시작합니다.
- a[j]가 b[k]보다 작거나 같으면 a[j]를 c[i]에 저장하고 j를 1 증가시킵니다.
- 그렇지 않으면 b[k]를 c[i]에 저장하고 k를 1 증가시킵니다.
- 세 번째 배열 c가 모두 채워질 때까지(총 o = m + n번) 위 과정을 반복합니다.
전체 프로그램 코드
다음은 C 언어로 두 배열을 병합하는 전체 프로그램입니다. 병합 전에 버블 정렬(Bubble Sort)을 사용해 각 배열을 오름차순으로 정렬한 뒤 병합을 수행합니다.
#include<stdio.h>
#include<stdlib.h>
int main(){
int a[10],b[10],c[20],m,n,o,i,j,k,temp;
printf("Enter size of Array1\n");
scanf("%d",&n);
printf("Enter size of Array2\n");
scanf("%d",&m);
o=m+n; // 세 번째 배열의 크기
printf("Enter Elements of Array1\n");
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
printf("Enter Elements of Array2\n");
for(i=0;i<m;i++){
scanf("%d",&b[i]);
}
// 첫 번째 배열 정렬
for(i=0;i<n;i++){
for(j=0;j<n-1-i;j++){
if(a[j]>a[j+1]){
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
// 두 번째 배열 정렬
for(i=0;i<m;i++){
for(j=0;j<m-1-i;j++){
if(b[j]>b[j+1]){
temp=b[j];
b[j]=b[j+1];
b[j+1]=temp;
}
}
}
printf("Elements of Array1\n");
for(i=0;i<n;i++){
printf("a[%d]=%d\n",i,a[i]);
}
printf("Elements of Array2\n");
for(i=0;i<m;i++){
printf("b[%d]=%d\n",i,b[i]);
}
j=0;
k=0;
for(i=0;i<o;i++){ // 두 배열 병합
if(a[j]<=b[k]){
c[i]=a[j];
j++;
}
else{
c[i]=b[k];
k++;
}
}
printf("Merged array is :\n");
for(i=0;i<o;i++){
printf("c[%d]=%d\n",i,c[i]);
}
}실행 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.
Enter Elements of Array1 1 2 3 4 Enter Elements of Array2 6 8 3 Elements of Array1 a[0]=1 a[1]=2 a[2]=3 a[3]=4 Elements of Array2 b[0]=3 b[1]=6 b[2]=8 Merged array is: c[0]=1 c[1]=2 c[2]=3 c[3]=3 c[4]=4 c[5]=6 c[6]=8
정리 및 참고 사항
이 예제에서는 입력된 배열을 먼저 정렬한 후 병합하기 때문에, 정렬되지 않은 배열도 올바르게 처리할 수 있습니다. 다만 버블 정렬의 시간 복잡도는 O(n²)이므로 데이터가 많아지면 성능이 떨어질 수 있습니다. 실무에서는 퀵 정렬이나 병합 정렬처럼 더 효율적인 정렬 알고리즘을 함께 사용하는 것이 좋습니다. 만약 두 배열이 이미 정렬되어 있는 상태라면, 정렬 과정 없이 병합 단계만 수행하면 되므로 O(n+m)의 시간 복잡도로 매우 빠르게 처리할 수 있습니다.