병합정렬(Merge Sort)

병합정렬은 원소들을 반으로 나누고 계산(정렬)한 후 나중에 합치는 것이다.

 

배열 {7,6,5,8,3,5,9,1} 이 있다고 가정하였을 때 오름차순으로 정렬을 시도한다면,

 

7  6  5  8  3  5  9  1 --> 크기가 1인 배열로 개별적으로 나눈다.

 

7  6  5  8  3  5  9  1 --> 67  58  35  19 --> 2개씩 묶도록 하며, 각각의 정렬 처리를 한다.

 

67  58  --> 5678 --> 67과 58을 비교하여 정렬 처리를 한다.

 

35  19  --> 1359 --> 35와 19를 비교하여 정렬 처리를 한다.

 

5678  1359 --> 13556789 --> 5678과 1359를 비교하여 정렬 처리를 한다.

 

=> 최종적으로 1 3 5 5 6 7 8 9 가 이루어진다. 

 

 

[예제]

#include <stdio.h>

int num = 8;
int sorted[8];

void merge(int a[], int start, int middle, int end) {
	int i = start;
	int j = middle + 1;
	int k = start;
	while(i <= middle && j <= end) {
		if(a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		} else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
	if(i > middle) {
		for(int t=j; t<=end; t++) {
			sorted[k] = a[t];
			k++;
		}
	} else {
		for(int t=i; t<=middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	for(int t=start; t<=end; t++) {
		a[t] = sorted[t];
	}
}

void mergeSort(int a[], int start, int end) {
	if(start < end) {
		int middle = (start + end) / 2;
		mergeSort(a, start, middle);
		mergeSort(a, middle+1, end);
		merge(a, start, middle, end);
	}
}

int main() {
	int array[num] = {7, 6, 5, 8, 3, 5, 9, 1};
	mergeSort(array, 0, num - 1);
	for(int i=0; i<num; i++) {
		printf("%d ", array[i]);
	}
}

 

정렬될 배열을 추가적으로 전역 변수로 선언해주고 merge() 함수에서 값을 비교하여 값이 작은 순서대로 배열에

 

삽입한다. 데이터를 비교하여 배열에 삽입하고 남은 데이터도 차례로 삽입한다. 최종적으로 전역변수 sorted[]에

 

값들이 정렬되어 있는데, 반복문을 통해 원래 배열에 정렬된 배열을 삽입해준다.

 

mergeSort() 함수에서는 재귀 함수를 활용하고 배열을 정확하게 반씩 나누도록 한다.

 

[결과]

병합정렬(Merge Sort) 결과

 

[병합 정렬의 시간 복잡도]

병합 정렬의 시간 복잡도는 O(N * logN) 이다.

 

데이터의 개수가 N개일 때 logN을 유지하고 정렬 자체에 필요한 수행시간은 N이므로 데이터의 개수만큼만

 

연산하면 된다. 또한, 병합 정렬은 정확히 반으로 나눈다는 점에서 최악 시간 복잡도도 O(N * logN) 이다.

 

---

출처

https://blog.naver.com/ndb796/221227934987

7. 병합 정렬(Merge Sort)