2개의 정렬된 정수 배열 A[]와 B[] 가 있다고 가정하자. 2개의 배열을 합쳐서 하나의 정렬된 배열 C[]로 만든느 함수를 작성하고 테스트한다. 다음과 같은 함수 원형을 가진다고 가정하라.
void merge(int *A, int *B, int *C, int size){...}
여기서 배열 A[], B[]는 똑같은 크기로 정의되어 있다고 가정한다. 배열 C[]에는 충분한 공간이 확보되어 있다고 가정하자. 합치는 알고리즘은 다음과 같다. 먼저 A[0]와B[0]를 비교한다. 만약 A[0]가 B[0]보다 작으면 A[0]를 C[0]에 복사한다. 다음에는 A[1]과 B[0]를 비교한다.이번에는 B[0]가 A[1]보다 작다면 B[0]를 C[1]에 저장한다. 똑같은 방식으로 남아있는 원소들을 비교하여 더 작은 원소를 C[]로 복사한다. 만약 A[]나 B[]중에서 어느 하나가 먼저 끝나게 되면 남아있는 원소들을 전부 C[]로 이동한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | #include <stdio.h> #define SIZE 4 void merge(int *A, int *B, int *C, int size); int main(void) { int A[SIZE]={2,5,7,8}; int B[SIZE]={1,3,4,6}; int C[SIZE*2]={0}; int i; printf("배열A: "); for(i=0;i<SIZE;i++) printf("%d ", A[i]); printf("\n"); printf("배열B: "); for(i=0;i<SIZE;i++) printf("%d ", B[i]); printf("\n"); merge(A,B,C,SIZE*2); printf("배열C: "); for(i=0;i<SIZE*2;i++) printf("%d ", C[i]); printf("\n"); return 0; } void merge(int *A, int *B, int *C, int size) { int i,j,k; i=0;j=0;k=0; for(k=0;k<size;k++) { if(i>=size/2) { C[k]=B[j]; j++;} else if(j>=size/2) { C[k]=A[i]; i++;} else if(A[i]<B[j]) {C[k]=A[i]; i++;} else if(A[i]>B[j]) {C[k]=B[j]; j++;} } } | cs |