5. 병합 정렬( merge sort)

이번에는 병합 정렬에 대해 알아보자.

병합 정렬의 경우, 퀵 정렬과 마찬가지로 시간복잡도가 O(N*logN)이다.

 

퀵 정렬은 최악의 경우에는 O(N^2) 까지도 늘어날 수가 있지만,

병합 정렬의 경우 최악의 경우에도 O(N*LogN)을 보장함으로써 아주 빠른, 훌륭한 정렬 방법이라고 볼 수 있다.

 

다음 숫자들을 일렬로 정렬하는 알고리즘을 작성하시오.
7  6  5  8  3  5  9  1

 

병합정렬 또한 분할 정복(divide and conquer) 가 기본 아이디어이다.

하나의 큰 문제를 두 개의 작은 문제로 분할한 뒤 각자 계산하고 나중에 합친다.

문제에서 8개의 숫자가 있는데 모두 낱개로 분해한 뒤에, 2개씩 합쳐나가는 것이다.

시작 단계에서는 정렬 안된 낱개의 8개 숫자가, 각 단계를 거치면서 2개씩 묶어서 정렬하는 것이다.

M번째 단계에서 정렬된 배열의 크기가 2배씩 늘어나므로, 높이는 밑이 2인 logN이다.

높이가 logN인건 알겠는데, 그럼 정렬하는데 O(N)이라는 소리인데, 어떻게 가능할까?

 

1단계 -> 2단계 상황을 보자.

6   7    5   8

두 작은 배열을 큰 하나의 배열로 합치기 전에, 두 작은 배열은 이미 정렬되어 있다.

따라서 정렬된 배열을 한번 쭉 읽어주기만 하면된다.

각 배열의 인덱스를 가리키는 i, j와 새로운 배열의 인덱스를 가리키는 k 가 있다.

우리가 할 일은 arr[i] 와 arr[j] 값을 비교한 뒤 더 작은 값을 차례대로 k가 가리키는 곳에 채워넣기만 하면 된다. 

 

i, j가 마지막에 도달하면 가리키는 숫자인 7, 8을 비교해 삽입한다.

이렇게 각 단계에서 총 N번의 연산 횟수를 가진다.

세로 = logN , 가로 N 이므로 전체 시간복잡도 O(N*logN)이다.

 

 

소스코드

#include<iostream>
using namespace std;
int sorted[8];

void merge(int arr[], int m, int n) {
	int mid = (m + n) / 2;
	int i = m, j = mid + 1, k = m;

	while (i <= mid && j <= n) {
		if (arr[i] >= arr[j]) {
			sorted[k] = arr[j];
			j++;
		}
		else {
			sorted[k] = arr[i];
			i++;
		}
		k++;
	}

	// 남은 데이터도 삽입
	if (i > mid) {
		while (j <= n) {
			sorted[k++] = arr[j];
			j++;
		}
	}
	else {
		while (i <= mid) {
			sorted[k++] = arr[i];
			i++;
		}
	}

	for (int t = m; t <= n; t++) {
		arr[t] = sorted[t];
	}
}

void mergeSort(int arr[], int m, int n) {
	if (m < n) {
		int middle = (m + n) / 2;
		mergeSort(arr, m, middle);
		mergeSort(arr, middle + 1, n);
		merge(arr, m, n);
	}
}

int main(void) 
{
	int arr[8] = { 7,6,5,8,3,5,9,1 };
	mergeSort(arr, 0, 7);
	for (int i = 0; i < 8; i++) {
		cout << arr[i] << " ";
	}
	return  0;
}