5강 - 병합 정렬 (Merge Sort)

1. 병합 정렬

1) 정의

 

2) 특징

1> 분할 정복 알고리즘(divide and conquer)의 하나

2> 시간 복잡도: 

- 편향된 분할을 하는 퀵 정렬과 달리

- 정확히 절반으로 분할을 해서 O(nlogn)을 보장한다.

3> 안정 정렬

4> 일단 반으로 쪼개고 나중에 합친다.

3) 퀵 정렬과 다른 점

1> pivot이 없다.

2> 그래서 항상 반으로 분할한다. (편향된 분할을 하지 않는다.)

 

 

2. 구체적인 과정

(오름차순 기준)

0> 해당 분할의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.

1> 계속해서 2등분으로 잘게 잘라놓는다.

2> 맨 처음 2개의 분할을 가지고 진행한다.

3> (각 분할은 이미 정렬되어 있다) 각 분할의 가장 맨 앞의 값을 비교하여 작은 값을 다른 array(sorted)의 같은 index(merged_index)에 넣는다.

4> 그리고 하나씩 다음 element를 다른 index(left_start or right_start)로 지정한다.

5> 또 비교해서 작은 값을 다른 array(sorted)의 같은 index(merged_index)에 넣는다.

6> 하나의 분할이 element가 남을텐데 다른 array(sorted)의 남은 자리에 차례로 넣는다.

7> 2>~6>의 과정이 끝나면 다시 원래 array(arr)에 넣어준다.

8> 그리고 그 다음 분할을 2>~7>에 대해 병합 정렬을 한다.

 

 

 

3. 구현

1) 중요 point

1> 일단 MAX 크기의 정렬된 array를 전역변수로 선언한다.

- 여러 함수를 넘나들며 array의 원소들이 필요하기 때문

- 작은 분할들을 필요한만큼 계속해서 할당할 바에 처음부터 큰 array를 만든다.

2> 2가지 함수를 구현한다.

- 일단 정확히 나누고 (mergeSort)

- 나중에 하나씩 병합 정렬 (merge)

 

#include <iostream>
using namespace std;
const int MAX = 1000;

int sorted[MAX]; // 정렬할 때 잠시 이용하는 array
int arr[MAX];

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

void merge(int arr[], int start, int middle, int end)
{
	int left_start = start; // 왼쪽 분할 맨 앞
	int right_start = middle + 1; // 오른쪽 분할 맨 앞
	int merged_start = start; // 병합 array의 맨 앞
	// 작은 순서대로 array에 삽입
	while (left_start <= middle && right_start <= end)
	{
		if (arr[left_start] <= arr[right_start])
		{
			sorted[merged_start] = arr[left_start];
			left_start++;
		}
		else
		{
			sorted[merged_start] = arr[right_start];
			right_start++;
		}
		merged_start++;
	}
	// 남은 data도 삽입
	if (left_start > middle)
	{
		while (right_start <= end)
		{
			sorted[merged_start] = arr[right_start];
			right_start++;
			merged_start++;
		}
	}
	else
	{
		while (left_start <= middle)
		{
			sorted[merged_start] = arr[left_start];
			left_start++;
			merged_start++;
		}
	}
	// 정렬을 위해 잠시 이용한 sorted에서 실제 array인 arr로 이동
	for (int i = start; i <= end; i++)
	{
		arr[i] = sorted[i];
	}
}

// !! 일단 정확히 반으로 나누고 (mergeSort)
// !! 나중에 정렬(merge)
void mergeSort(int *arr, int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;
		mergeSort(arr, start, middle);
		mergeSort(arr, middle + 1, end);
		merge(arr, start, middle, end);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	mergeSort(arr, 0, N - 1);
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}

 

 

 

cf> 이해를 위한 그림