[알고리즘] Merge Sort

병합 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 정렬 알고리즘이다

병합정렬 순서 (쉽게)

1. 재귀함수를 이용해서 원소가 들어있는 리스트를 균등하게 2개의 부분 배열로 나눈다

2. 분할하는 함수 안에 재귀적으로 분할함수가 들어있고, 그냥 병합함수가 들어있다

3. 각 부분 배열이 분할을 진행한 뒤 바로 정렬하여 임시배열에 넣고, 정렬된 배열을 원본 배열에 복사한다

4. 임시 배열을 해제한다 (임시배열은 재귀 함수가 호출될 때마다 각각의 부분 배열에 대하여 새로 생성된다)

병합정렬 전체코드

#include <iostream>
#define SIZE 8
using namespace std;

void Merge(int list[], int start, int middle, int end)
{
	int count = 0;
	
	int left = start;
	int right = middle + 1;

	// 동적 배열 크기 
	int* array = new int [end - start + 1] {0, };

	// 두 부분의 배열을 병합합니다(오름차순)
	while (left <= middle && right <= end)
	{
		if (list[left] <= list[right])
		{
			array[count++] = list[left++];
		}
		else
		{
			array[count++] = list[right++];
		}
	}
	
	// 남은 왼쪽 배열의 요소들을 복사합니다
	while (left <= middle)
	{
		array[count++] = list[left++];
	}

	// 남은 오른쪽 배열의 요소들을 복사합니다
	while (right <= end)
	{
		array[count++] = list[right++];
	}

	// 원본 배열에 정렬된 임시 배열의 값을 복사합니다
	for (int i = 0; i < end - start + 1; i++)
	{
		list[start + i] = array[i];
	}

	delete[] array;
}


void MergeSort(int list[], int start, int end)
{
	if (start < end)
	{
		int middle = (start + end) / 2;

		MergeSort(list, start, middle);
		MergeSort(list, middle + 1, end);

		Merge(list, start, middle, end);
	}
}

int main()
{
#pragma region 병합 정렬

	int list[SIZE] = { 21, 10, 12, 20, 25, 13, 15, 22 };

	MergeSort(list, 0, SIZE - 1);

	for (const int& element : list)
	{
		cout << element << " ";
	}

#pragma endregion



	return 0;
}

결과값:

---

병합정렬 과정

1.분할과정
-> 재귀함수를 사용하여 middle값을 기준으로 계속 2개의 부분 배열로 나눈다
-> 각 함수를 돌때마다 start와 end의 기준이 달라져서 middle값은 계속 바뀐다
-> 배열의 사이즈가 1이거나 0이면 재귀함수를 종료한다
즉, 배열의 크기가 1이 될때까지만 분할한다

2. 병합과정
   -> 분할 함수를 보면 재귀함수를 호출하여 두 부분배열로 만든 뒤, 바로 병합하는 함수가 실행된다
   -> 즉, 분할하고 두 부분배열을 바로 정렬해서 임시배열에 넣고, 기존 배열에 값을 복사하는 것!!
   -> 재귀함수를 계속해서 호출하고 배열의 크기가 1이 될때까지 분할한다. 재귀함수를 탈출하면 각 함수에서 아직 실행하지 않은 남은 로직을 수행해야한다(그것이 병합함수 로직)

   처음에 이해를 제대로 못해서 나는 분할을 모두 한 뒤에 각각의 임시배열들 안에 이 값을 정렬해두고 마지막에 기존 배열에 다 값을 복사하는 줄 알았다. 근데 아니었다

   • 각각의 임시배열들은 재귀함수가 호출될때마다 동적으로 생성되고 해제되는 것. 그렇기 때문에 바로 정렬해서 기존 배열에 값을 복사해야한다

3. 병합과정 자세히
   -> 분할된 배열의 요소들이 left와 right를 가지고 서로 값을 비교한 뒤, 임시배열에 값을 저장해둔다
   -> 임시 배열 크기가 가득찼다면 해당 배열의 정렬이 완료된 것으로 기존의 배열에 값을 복사한다
   
   -> 한 단계의 분할을 거치면 바로 정렬된 배열이 기존배열이 된다
   

4. 임시 배열의 크기
   -> 병합함수가 호출되면 동적으로 임시 배열이 생성된다
   -> 크기는 end - start + 1
   -> 예를 들면, start = 0 , end = 3의 인덱스일때 (3 - 0 ) + 1 해서 배열의 크기는 4로 잡힌다
   
   

5. 요소 비교 자세히

• 1. 두 부분 배열을 비교하기 위해서 왼쪽 배열의 시작점을 left, 오른쪽 배열의 시작점을 right로 지정한다
     

  2. left와 right값을 비교하여 더 작은 값을 임시배열에 넣고 count++ (오름차순 정렬)
     

  3. left와 right값 중 하나라도 범위를 벗어나면 병합하는 반복문이 종료된다

  4. 한쪽이 범위를 벗어나면 다른쪽 배열은 아직 값이 남아있기 때문에 임시배열에 복사해줘야한다
     

  5. 해당 함수가 종료될 때까지 임시배열에 정렬을 완료한 뒤, 기존의 배열에 값을 복사하고 임시배열은 동적으로 할당했기 때문에 해제해준다
     

---

병합정렬 시간복잡도

병합정렬은 기본 분할정복을 사용한 정렬 방법이다

• 배열을 재귀함수를 이용하여 반으로 쪼개고, 배열의 크기가 가장 작은 사이즈가 될때까지 분할한다

1. 분할정복과 동일하게 깊이는 O(logN)

정확히 말하자면, 비교 연산부분은 N - 1번 수행한다
-> 왜냐하면 마지막 원소는 다른 원소들이 다 비교된 후 남기 때문에 자동으로 정렬된다고 본다
-> !! 하지만, 비교 하는 것 자체는 N - 1번이라도 배열을 병합하는 과정 자체가 연산의 일환이기 때문에, 결국 N개의 원소가 병합될때 N번 연산이 이루어지는 것

2. 연산은 logN깊이로 각 단계마다 N번씩 다 비교하고 수행하기 때문에 N * logN 으로 시간복잡도는 O(NlogN)이다
   

---

병합정렬 다시보기

퀵정렬에서도 실수했는데 또 실수했다...
후위증가 좀 빼먹지 말자 ...ㅠㅡㅠ

#include <iostream>
#define SIZE 8
using namespace std;

void MergeSort(int list[], int start, int middle, int end)
{
	int left = start;
	int right = middle + 1;

	int count = 0; // 임시배열 카운팅

	// 배열의 크기
	int * array = new int[end - start + 1];


	// 반복문 조건이 끝났다는 건 left와 right 둘 중 하나가 범위를 벗어난 것
	while (left <= middle && right <= end)
	{
		// 후위정렬이라 작은값을 임시배열로 넣기
		if (list[left] <= list[right])
		{
			array[count++] = list[left++];
		}
		else if (list[right] <= list[left])
		{
			array[count++] = list[right++];
		}
	}

	// 남은 배열의 값 복사
	while (left <= middle)
	{
		array[count++] = list[left++];
	}
	while (right <= end)
	{
		array[count++] = list[right++];
	}

	// 기존 배열에 값을 복사
	for (int i = 0; i < end - start + 1; i++)
	{
		list[start + i] = array[i];
	}

}





// 분할 함수(middle값을 기준으로 부분배열 나누기)
void Merge(int list[], int start, int end)
{
	int middle = (start + end) / 2;

	if (start < end)
	{
		// 각 부분 배열로 재귀함수 실행
		Merge(list, start, middle);
		Merge(list, middle + 1, end);

		MergeSort(list, start, middle, end);
	}

}

int main()
{
	int list[SIZE] = { 9,5,6,4,3,1,2,7 };

	Merge(list, 0, SIZE - 1);

	for (const int& element : list)
	{
		cout << element << " ";
	}


	return 0;
}

---

1. 병합정렬은 매번 새로운 메모리를 동적할당 해야하기 때문에 추가적인 메모리 공간이 필요하다
2. 상대적으로 메모리 사용량이 많다