[알고리즘] 병합 정렬

병합 정렬 : 피벗 값이 없고 일단 정확히 반으로 자르고 나중에 정렬

-> 퀵 정렬과 마찬가지로 ' 분할 정복' 방법을 채택한 알고리즘

​

정확하게 반절씩 나눈다는 점에서 최악의 경우에도 O(N * logN)의 시간 복잡도를 가진다.

​

76583519를 병합 정렬을 사용하여 정렬한다고 했을 경우

시작 : 7 6 5 8 3 5 9 1

1 : 67 58 35 19로 2개씩 묶어서 2개씩 각각 정렬해 준다.

2 : 5678 1359로 4개씩 묶어 4개씩 각각 정렬해 준다.

3 : 13556789 ​로 하나로 합치며 정렬하여 준다.

​

이때 폭을 N 높이를 log2N이라고 한다.

즉, 위 정렬은 8 * log28(3) 번 연산을 한다.

1번에서 8번 -> 76 정렬 때 2번, 58 정렬 때 2번, 35 정렬 때 2번, 91 정렬 때 2번 = 8

2번에서 8번 -> 67 58 정렬 때 4번, 35 91 정렬 때 4번 = 8번

-> 67 58 정렬 방법은

67 58 -> 6 5 비교 5가 작기 때문에 5가 제일 앞 5 _ _ _

-> 6 8 비교 6이 작기 때문에 5 다음 6 5 6 _ _

-> 7 8 비교 7이 작기 때문에 6 다음 7 5 6 7 _

-> 나머지 8 5 6 7 8

====> 총 4번 연산

3번에서 8번 -> 5678 1359 정렬 때 8번 = 8번

​

====> 총 24번 연산 => 8 * 3

​

그렇기 때문에 병합 정렬의 시간 복잡도는 O(N * log2N)이다.

병합 정렬의 시간 복잡도

O(N * logN)

 

#include<stdio.h>

#define num 8
int sorted[8];                     // 합칠때 마다 배열이 필요하기 때문에 메모리 소모를 줄이기 위해서 
                                   // 정렬 배열은 반드시 전역변수로 선언하여 모든 함수가 공통으로 사용
void merge(int a[], int m, int middle, int n) {
	int i = m;
	int j = middle + 1;   // (7  6)  (5  8) 정렬시 middle 값은 0 + 3 / 2 
	int k = m;			  // 즉 1이기 때문에 6의 자리에 값이기 때문에 +1을 해주어 j는 2 => 5부터 시작이다
//  작은 순서대로 배열에 삽입

	while ( i <= middle && j <= n){
		if (a[i] <= a[j]) {
			sorted[k] = a[i];
			i++;
		}
		else {
			sorted[k] = a[j];
			j++;
		}
		k++;
	}
//  남은 데이터 삽입  -> 위 예시 2번에서 67 58 연산시 마지막 8의 경우를 대비하여
	if (i > middle) {    // i가 먼저 배열에 삽입 되었을 경우
		for (int t = j; t <= n; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
	else {              // j가 먼저 배열에 삽입 되었을 경우
		for (int t = i; t <= middle; t++) {
			sorted[k] = a[t];
			k++;
		}
	}
//  마지막 정렬된 배열을 삽입
	for (int t = m; t <= n; t++) {
		a[t] = sorted[t];   
	}
}

void mergeSort(int a[], int m, int n) {  // 병합 정렬인 경우 재귀함수를 사용하면 쉽게 구현이 가능하다.
//  크기가 1보다 큰 경우
	if(m < n){
		int middle = (m + n) / 2;
		
		mergeSort(a, m, middle);        // m과 middle 사이에서 array[]배열을 정렬
		mergeSort(a, middle + 1, n);    // middle + 1과 n 사이에서 array[]배열을 정렬
		merge(a, m, middle, n);
	}
}

int main(void) {
	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]);
}

​

병합 정렬을 구현할 때 신경써야 하는 부분은 정렬에 사용되는 배열 sorted 배열을 반드시 '전역변수'로 선언해야 한다는 것이다.

함수 안에 배열을 선언할 경우 매 번 배열을 선언해야 한다는 점에서 메모리 자원의 낭비가 커질 수 있기 때문입니다.

​

이와 같이 병합 정렬은 기존 데이터를 담을 추가적인 배열 공간이 필요하다는 점에서 메모리 활용이 비효율적이란 문제와 일반적인 경우 퀵 정렬보다 느리다는 점이 있지만

​

어떠한 상황에도 정확이 O(N * logN)을 보장한다는 점에서 몹시 효율적인 알고리즘이다.