6-7장 병합 정렬

1. 정렬을 마친 배열 병합하기 

 

- '각 배열에서 선택한 요소의 값을 비교하여 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업'을 반복하여 

정렬을 끝냄

- 병합에 필요한 시간 복잡도 

 O(n)

 

 

a와 b의 배열을 비교하여 작은 값을 꺼내 c에 넣음

 

- 정렬을 마친 배열을 병합하는 프로그램

//정렬을 마친 배열을 병합하는 프로그램
#include <stdio.h> 
#include <stdlib.h>

void merge(const int a[], int na, const int b[], int nb, int c[])
{
	int pa = 0;
	int pb = 0;
	int pc = 0;
	while(pa < na && pb <nb)
		c[pc++] = (a[pa]<=b[pb]) ? a[pa++] : b[pb++];
	while(pa < na)
	    c[pc++] = a[pa++];
	while(pb < nb)
		c[pc++] = b[pb++];
}

int main()
{
	int na,nb;
	printf("a 요소 개수:"); scanf("%d",&na);
	printf("b 요소 개수:"); scanf("%d",&nb);
	int *a = (int *)calloc(na, sizeof(int));
	int *b = (int *)calloc(nb, sizeof(int));
	int *c = (int *)calloc(na+nb, sizeof(int));
	printf("a[0]:");
	scanf("%d",&a[0]);
	for(int i = 1; i <na; i++) {
		do{ 
		 printf("a[%d]:", i);
		 scanf("%d",&a[i]);
		}while(a[i]<a[i-1]);
	}
	printf("b[0]:");
	scanf("%d",&b[0]);
	for(int i = 1; i <nb; i++) {
		do{ 
		 printf("b[%d]:", i);
		 scanf("%d",&b[i]);
		}while(b[i]<b[i-1]);
	}
	
	//배열 a와 b를 병합하여 c에 저장
	merge(a,na,b,nb,c);
	puts("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
	for(int i=0; i<na+nb; i++)
		printf("c[%2d]=%2d\n",i,c[i]);
	free(a);
	free(b);
	free(c);
	
	return 0;
	
		
}

 

- merge함수

 - 요소의 개수가 na개인 배열 a와 요소의 개수가 nb개인 배열 b를 병합하여 배열 c에 저장 

 

 - pa : 배열 a의 인덱스 

   pb : 배열 b의 인덱스  

   pc : 배열 c의 인덱스 

 

1) 배열 a에서 선택한 요소(a[pa])와 배열 b에서 선택한 요소(b[pb])를 비교하여 작은값을 c[pc]에 저장

   - pb,pc를 한칸 옮기고 pa는 그대로 둠  (pa가 큰 경우)

   - pa가 배열 a의 끝에 다다르거나, pb가 배열 b의 끝에 다다를때까지 반복

while(pa < na && pb <nb)
	c[p++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];

 

2) while문 실행 조건은 1)의 과정을 통해 배열 b의 모든 요소를 배열 c로 복사하고

  배열 a에는 아직 복사하지 못한 요소가 남아있는 상태를 전제로 함

 - pa를 한칸씩 진행하면서 복사하지 않은 모든 배열 a의 요소를 배열 c에 복사 

while(pa<na)
	c[pc++] = a[pa++];

 

3) while문 실행 조건은 1)의 과정을 통해 배열 a의 모든 요소를 배열 c로 복사하고 

   배열 b에는 아직 복사하지 못한 요소가 남아있는 상태를 전제로 함

  -pb를 한칸씩 진행하면서 복사하지 않은 모든 배열 b의 요소를 배열 c에 복사 

while(pb<nb)
	c[pc++] = b[pb++];

 

 

2. 병합 정렬하기 

 

병합 정렬 (merge sort)

- 정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘

- 배열의 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복

 

- 분할 정복법

 1) 분할(Divide) 

  : 해결이 용이한 단계까지 문제를 분할

 2) 정복(Conquer)

  : 해결이 용이한 단계까지 문제를 해결

 3) 결합(Combine)

  : 분할해서 해결한 결과를 결합하며 마무리 

 

- 병합 정렬 알고리즘

 -> 배열의 요소 개수가 2개 이상인 경우 

 1) 배열의 앞부분을 병합 정렬로 정렬

 2) 배열의 뒷부분을 병합 정렬로 정렬

 3) 배열의 앞부분과 뒷부분을 병합 

 

 

- 병합 정렬 프로그램

//병합 정렬 프로그램

#include <stdio.h> 
#include <stdlib.h>

static int *buff; //작업용 배열

//병합 정렬(main)
static void __mergesort(int a[], int left, int right) 
{
	if(left <right) {
		int center= (left +right)/2;
		int p = 0;
		int i;
		int j = 0;
		int k = left;
		__mergesort(a,left,center); //앞부분에 대한 병합 정렬
		__mergesort(a,center+1,right); //뒷부분에 대한 병합 정렬
		for(i = left; i <= center; i++)
			buff[p++] = a[i];
		while(i <= right && j <p)
			a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
		while(j < p)
			a[k++] = buff[j++];
	}
}

//병합 정렬 함수 
int mergesort( int a[], int n) 
{
	if((buff=(int*)calloc(n,sizeof(int))) == NULL)
		return -1; 
	__mergesort(a,0,n-1); //배열 전체를 병합 정렬
	free(buff);
	return 0;
}

int main()
{
	int nx;
	puts("병합 정렬 ");
	printf("요소 개수:");
	scanf("%d",&nx);
	int *x =(int *)calloc(nx,sizeof(int));
	
	for(int i=0; i <nx; i++) {
		printf("x[%d]:",i);
		scanf("%d",&x[i]);
	}
	
	mergesort(x,nx); //배열 x를 병합정렬
	puts("오름차순으로 정렬했습니다.");
	for(int i = 0; i <nx; i++)
		printf("x[%d]=%d\n",i,x[i]);
	free(x); //배열 x를 해제 
	
	return 0; 
	
}

 

 

- 정렬을 마친 앞부분과 뒷부분의 병합은 작업용 배열 buff를 사용

- 병합을 수행하는 순서 

 

1) 배열의 앞부분(a[left] ~ a[center])을 buff[0] ~ buff[center-left]로 복사. for문이 끝날때 p값은 복사한 요소의 개수 center -left +1이 됨

for(i = left; i <= center; i++)
	buff[p++] = a[i];

 

 2) 배열의 뒷부분 (a[center+1] ~ a[right]과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장

while(i <= right && j<p)
	a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];

 

3) 배열 buff에 남아 있는 요소를 배열 a로 복사

while(j<p)
	a[k++] = buff[j++];