2. 분할정복 - 병합정렬

병합정렬이란?

주어진 수열을 범위를 나누어 정렬하는 방법이다. 우선 모든 수열을 잘게 쪼개는 분할의 과정을 거치고 나누어진 수열을 차례대로 정렬한 뒤 합친다. 

 

다음은 병합정렬을 표현한 예이다.

 

 

위에서 설명한 것 처럼 가장 작은 단위로 분할한 뒤에 큰 쪽으로 합쳐가는 것을 알 수 있다. 따라서 알고리즘을 설계할 때, 분할하는 부분과 정렬하여 합치는 부분 두가지로 나누어 설계해야한다.

 

시간복잡도

병합정렬은 항상 시간 복잡도 O(nlogn)을 유지한다. 따라서 데이터 분포에 영향을 받지 않는다.

 

구현

병합정렬 구현은 다음과 같다.

#include <iostream>
#include <vector>
using namespace std;

int cnt = 1; //정렬이 진행된 횟수

void merge(vector<int> &v, int low, int mid, int high) {
	int i = low, j = mid + 1, where = 0;
	vector<int> temp; //원하는 범위에서 정렬된 상태를 담는 변수

	//두 가지의 범위를 놓고 서로 비교하여 작은 순서대로 temp안에 삽입한다.
	//삽입이 된 범위는 반복자에 1을 더한다.
	while (i <= mid && j <= high) {
		if (v[i] < v[j]) {
			temp.push_back(v[i]);
			i++;
		}
		else {
			temp.push_back(v[j]);
			j++;
		}
	}
	
	//비교 과정에서 놓쳤던 것들을 현재 비교했던 대상에 넣는다.
    //직전 과정에서 나뉜 부분을 정렬된 상태로 저장해놓았기 때문에 차례대로 넣어도 무방하다.
	//남아 있는 부분을 모두 삽입하면 temp의 원소로 항상 high - low + 1개가 들어간다.
	if (i > mid) {
		for (int iter = j; iter <= high; iter++) {
			temp.push_back(v[iter]);
		}
	}
	else {
		for (int iter = i; iter <= mid; iter++) {
			temp.push_back(v[iter]);
		}
	}
	
	//정렬한 위치에 대한 정보를 갱신
	for (int k = low; k <= high; k++) {
		v[k] = temp[where];
		where++;
	}

	cout << cnt << ": ";
	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << ' ';
	}
	cout << '\n';
	
	cnt++;
}

void mergesort(vector<int> &v,int low, int high) {
	int mid; //절반 위치 저장 변수
	if (low < high) {
		mid = (low + high) / 2;
		mergesort(v, low, mid); //바로 전 절반 앞 부분으로 분할
		mergesort(v, mid + 1, high); //바로 전 절반 뒷 부분으로 분할
		merge(v, low, mid, high); //병합
	}
}

int main() {
	vector<int> v;

	v.push_back(1);
	v.push_back(3);
	v.push_back(100);
	v.push_back(10);
	v.push_back(2);
	v.push_back(56);
	v.push_back(99);
	v.push_back(0);
	v.push_back(23);
	v.push_back(4);

	mergesort(v, 0, v.size() - 1);
}

 

다음은 결과이다.