[C++] 병합 정렬 (Merge sort) 개념 및 구현

# 합병 정렬

 

특징

1. 분할 정복 알고리즘

2. 동일한 원소 존재시, 원래의 순서를 보존하는 안정 정렬

3. 일반적으로 최고, 최악, 평균 시간 복잡도 O(N * logN)

4. 임시 버퍼의 필요로 공간 복잡도 O(N)

 

 

알고리즘

 

1. 입력 버퍼를 절반씩 분할하여 나눈 두 버퍼에 대해 각 재귀함수를 호출

2. 계속 나누면서 들어가다가, 버퍼의 크기가 1일 때 중단점을 걸어 반환

3. 재귀함수를 나오면서 두 버퍼의 첫 요소부터 비교하여 작은 요소부터 임시 버퍼에 복사

    (복사한 요소는 더이상 비교 대상이 아니며, 해당 버퍼의 index는 1 증가)

4. 복사한 구간의 임시 버퍼를 입력 버퍼에 복사

 

 

구현 및 상세 설명

#include <vector>

void sort(std::vector<int>& buf)
{
	std::vector<int> result(buf.size());
	recursion(buf, result, 0, buf.size()-1);
}

 

먼저 sort()에서 병합 정렬에서 사용할 임시 버퍼를 미리 할당하여 재귀 함수의 인자에 같이 삽입해준다.

 

static void recursion(std::vector<int>& buf, std::vector<int>& result, int start, int end)
{
	if (start == end)
		return;

	int middle = (start + end)/2;

	recursion(buf, result, start, middle);
	recursion(buf, result, middle+1, end);

	merge(buf, result, start, middle, end);

	for (int i=start; i<=end; ++i)
		buf[i] = result[i];
}

 

호출한 recursion()은 버퍼를 절반씩 나누며 들어가는데,

실제로 버퍼를 반으로 나누어 넣는 것은 오버헤드가 크기 때문에 start와 end index로 구분한다.

 

버퍼가 절반씩 나누어지고, 나눠진 버퍼들은 각각 정렬되어야 하기 때문에 두 번의 재귀함수를 호출한다.

 

재귀 함수의 호출은 start가 end와 같을 때까지 진행한다.
이는 나눠진 버퍼의 크기가 1이라는 것을 뜻한다.

 

static void merge(std::vector<int>& buf, std::vector<int>& result, int start, int middle, int end)
{
	int left = start;
	int right = middle + 1;

	for (int i=start; i<=end; ++i)
	{
		if (right > end || (left <= middle && buf[left] <= buf[right]))
			result[i] = buf[left++];
		else if (left > middle || (right <= end && buf[left] > buf[right]))
			result[i] = buf[right++];
	}
}

 

재귀가 풀리고 나올 때 병합이 시작된다.

아래는 중단점 이후 제일 처음 병합하는 과정이다.

 

 

left와 right는 각 버퍼의 맨 앞 요소를 가리킨다.

left와 right가 가리키는 요소끼리 비교하여 더 작은 요소를 result 버퍼에 담는다.

 

각 버퍼의 커서(left, right)가 버퍼의 끝에 도달했을 시, 반대편 요소를 담는다. (buffer overflow 방지)

 

이후 result를 담았던 구간 만큼만 buf (입력 버퍼)에 복사한다.

이로써 각 요소의 개수가 1개인 버퍼는 정렬된 상태가 보장된다.

 

본 알고리즘은 재귀적으로 이루어지기 때문에 2와 7이 정렬이 완료된 이후 4와 8도 같은 방식으로 정렬된다.

더 빠져나온 depth에선 2,7과 4,8이 각 버퍼를 이루며 이들은 아래와 같이 정렬된다.

 

 

result 버퍼는 알고리즘의 맨 마지막에서야 할당한 크기를 모두 사용하지만,

미리 한 번만 할당하는 것이 더 바람직할 것이다.

 

 

테스트

#include <vector>
#include <iostream>
#include <cstdlib>
#include "MergeSort.hpp"

static void sortChecker(std::vector<int>& buf)
{
	for (int i=0; i<(int)buf.size()-1; ++i)
	{
		if (buf[i] > buf[i+1])
		{
			std::cout << "\e[31mX\e[0m ";
			return;
		}
	}
	std::cout << "\e[32mV\e[0m ";
}

int main(int ac, char** av)
{
	if (ac < 2)
	{
		std::cout << "<Usage> : ./a.out 5 2 4 1 3\n";
		return 1;
	}

	std::vector<int> buf;
	buf.reserve(ac);

	for (int i=1; i<ac; ++i)
		buf.push_back(atoi(av[i]));

	merge::sort(buf);
	
	sortChecker(buf);
	return 0;
}

 

#!/bin/bash

# Linux
echo -n "1. Positive test : "
$1 `seq 0 0 | shuf | tr "\n" " "`
$1 `seq 0 2 | shuf | tr "\n" " "`
$1 `seq 1 100 | shuf | tr "\n" " "`
$1 `seq 1 100000 | shuf | tr "\n" " "`
$1 `seq 2147480000 2147483647 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "`
done
echo ""

echo -n "2. Negative test : "
$1 `seq -1 -1 | shuf | tr "\n" " "`
$1 `seq -2 0 | shuf | tr "\n" " "`
$1 `seq -100 -1 | shuf | tr "\n" " "`
$1 `seq -99999 -1 | shuf | tr "\n" " "`
$1 `seq -2147483648 -2147473648 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

echo -n "3. Integer test : "
$1 `seq -1 1 | shuf | tr "\n" " "`
$1 `seq -3 2 | shuf | tr "\n" " "`
$1 `seq -100 100 | shuf | tr "\n" " "`
$1 `seq -33121 32451 | shuf | tr "\n" " "`
$1 `seq -3 123123 | shuf | tr "\n" " "`
$1 `seq -112312 6 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "` `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

결과

 

 

전체 코드

https://github.com/SikPang/Algorithms/tree/main/MergeSort

 

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.