251126 언리얼엔진 본캠프 75일차 Merge Sort

병합 정렬(Merge Sort)

지난 시간에 우리는 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort), 빠른 정렬(Quick Sort)를 공부했었다. 오늘은 이것들과 다른 방식의 정렬인 병합 정렬에 대해서 공부해보려고 한다.

병합정렬은 배열을 계속해서 절반으로 쪼개고 더이상 쪼갤 수 없다면 쪼개어진 하위 배열들을 정렬하게 된다. 이 과정에서 크기가 1인 배열은 이미 정렬이 된 상태로 간주한다. 그 다음 정렬이 끝난 하위 배열들의 시작을 비교하여 정렬하여 하나의 배열로 합치는 과정으로 이루어져 있다. 코드로 한번 작성해보자

#include <iostream>
#include <vector>

using namespace std;

void Merge(vector<int>& nums, int begin, int mid, int end)
{
	vector<int> temp;

	int i = begin;
	int j = mid + 1;

	while (i <= mid && j <= end)
	{
		if (nums[i] <= nums[j])
		{
			temp.push_back(nums[i++]);
		}
		else
		{
			temp.push_back(nums[j++]);
		}
	}

	while(i<=mid)
	{
		temp.push_back(nums[i++]);
	}

	while (j <= end)
	{
		temp.push_back(nums[j++]);
	}

	for (int k = 0; k < temp.size(); ++k)
	{
		nums[begin + k] = temp[k];
	}
}

void MergeSort(vector<int>& nums, int begin, int end)
{
	if (begin < end)
	{
		int mid = begin + (end - begin) / 2;

		MergeSort(nums, begin, mid);
		MergeSort(nums, mid+1, end);

		Merge(nums, begin, mid, end);
	}
}

 

MergeSort함수와 Merge함수 2개를 이용하여 병합정렬을 구현해보았다. begin은 벡터의 시작 인덱스, end는 벡터의 끝 인덱스를 가리키며 mid는 벡터의 중앙을 가리키는 인덱스로 계산되게끔 하였다. MergeSort에서는 일단 주어진 벡터를 mid를 기준으로 분할한다. 함수재귀를 이용하여 더이상 나눌 수 없을 때 까지 나누게끔 한다. 그후 Merge를 호출한다. Merge함수가 호출되면 temp라는 임시 벡터를 생성한 뒤 맨 첫 인덱스부터 순회할 i와 mid+1부터 순회할 j를  지정해주고 i가 mid보다 작거나 같고 j가 end보다 작거나 같을 때 까지 벡터의 i와 j인덱스의 값을 비교하여 더 작은 값을 임시벡터 temp에 push_back하도록 반복한다. 그 다음 mid기준으로 왼쪽과 오른쪽에 값이 남아있다면 해당 값들도 push_back 해준 다음 임시 벡터의 값들을 기존 벡터에 대입해주는 반복문을 돌려준다. 이미지로 보자면 이런식이다.

출처 : Merge Sort (With Code in Python/C++/Java/C)

그림을 보면 각 원소 한 개씩 남도록 잘게 배열을 쪼갠 뒤 크기를 비교하여 정렬후 병합하는 과정을 통해서 최종 병합을 하는 방식이다.

 

그럼 Quick Sort와 Merge Sort는 어떨때 쓸까?

MergeSort는 기준점을 정하여 좌우로 나누어 정렬을 하는 Quick Sort와 유사한 점이 많다. 하지만 완전히 다른 성질을 갖고 있다. 빠른 정렬은 O(N logN)의 시간복잡도를 갖지만 최악의 경우에는 O(N^2)의 시간복잡도를 갖게 되며 메모리공간을 비교적으로 적게 쓰고 피벗을 정해 위치를 교환하는 방식이다. 병합 정렬은 시간 복잡도는 O(N log N)으로 동일하지만 최악의 경우에도 O(N logN)으로 빠른 정렬보다 빠르며 메모리 공간은 별도의 배열을 추가로 생성하기 때문에 빠른 정렬에 비해 많은 공간을 필요로 한다. 또한 기존의 배열을 나누어 새로운 배열에 병합하는 방식으로 구현하여 약간의 차이가 있다. 그렇기에 속도가 필요하고 메모리공간이 여유롭지 않고 일반적인 배열을 정렬할 때는 Quick 정렬을 연결 리스트와 같이 랜덤 접근이 어려운 방식의 자료구조를 정렬하거나 최소한의 속도를 보장받고 싶으면 Merge 정렬을 사용하면 되겠다.