[C++] 백준 2751 수 정렬하기 - 재귀, 병합정렬

#include <iostream>
#include <vector>

using namespace std;
vector<int> num;
vector<int> tempNum;

void MergeDivied(vector<int> *list, int left, int right);
void MergeSort(vector<int> &list, int left, int mid, int right);

int main()
{
	int n = 0;
	cin >> n;
	
	for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;
		num.push_back(temp);
		tempNum.push_back(0);
	}

	MergeDivied(&num, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << num[i] << "\n";
	}
}

void MergeDivied(vector<int> *list, int left, int right)
{
	if (left == right) return;

	int mid = 0;

	if (left < right)
	{
		mid = (left + right) / 2;
		MergeDivied(list, left, mid);
		MergeDivied(list, mid + 1, right);

		MergeSort(*list, left, mid, right);
	}
}

void MergeSort(vector<int> &list, int left, int mid, int right)
{
	int L, R, k, a;
	L = left;
	R = mid + 1;
	k = left;

	//왼쪽 항과 오른쪽 항의 비교하여 하나씩 대입
	while (L <= mid && R <= right)
		tempNum[k++] = list[L] <= list[R] ? list[L++] : list[R++];

	//남은 수를 대입 
	if (L > mid)
		for (a = R; a <= right; a++)
			tempNum[k++] = list[a];
	else
		for (a = L; a <= mid; a++)
			tempNum[k++] = list[a];

	//원래 배열에 저장
	for (a = left; a <= right; a++)
		list[a] = tempNum[a];
}

 

---

처음에 배열의 개수만큼 정렬한 수를 넣을 배열의 빈 공간을 만들어줍니다.

for (int i = 0; i < n; i++)
	{
		int temp = 0;
		cin >> temp;
		num.push_back(temp);
		tempNum.push_back(0);
	}

 

주소로 보내어 값이 변동하게 합니다.

MergeDivied(&num, 0, n - 1);

 

함수는 포인터로 해주어 주소를 받아줍니다.

void MergeDivied(vector<int> *list, int left, int right)

 

재귀함수로 반복합니다.

반복하면서 아래의 정렬을 할 함수를 통해 정렬을 합니다.

[재귀순서 아래 더보기 참고]

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

https://www.youtube.com/watch?v=FCAtxryNgq4&ab_channel=%EC%BD%94%EB%94%A9%ED%95%98%EB%8A%94%EA%B1%B0%EB%8B%88

 

void MergeDivied(vector<int> *list, int left, int right)
{
	if (left == right) return;

	int mid = 0;

	if (left < right)
	{
		mid = (left + right) / 2;
		MergeDivied(list, left, mid);
		MergeDivied(list, mid + 1, right);

		MergeSort(*list, left, mid, right);
	}
}

 

왼쪽 항과 오른쪽 항의 값을 비교하여 빈 배열에 하나씩 넣어줍니다.

L일 경우 다음항으로 넘어가기 위해 1씩 증가시키다가 mid와 L의 값이 같아지면 L쪽은 정렬이 되고 while문을 나갑니다.

void MergeSort(vector<int> &list, int left, int mid, int right)
{
	int L, R, k, a;
	L = left;
	R = mid + 1;
	k = left;

	//왼쪽 항과 오른쪽 항의 비교하여 하나씩 대입
	while (L <= mid && R <= right)
		tempNum[k++] = list[L] <= list[R] ? list[L++] : list[R++];

	

 

남은 정렬이 되지 않은 수를 차례로 정렬해줍니다. 

남은것이 L쪽이면 남은 L번째의 수부터 mid 중간까지 하나씩 넣어줍니다.

다 마치면 원래 배열에 정렬된 배열을 넣어줍니다.

//남은 수를 대입 
	if (L > mid)
		for (a = R; a <= right; a++)
			tempNum[k++] = list[a];
	else
		for (a = L; a <= mid; a++)
			tempNum[k++] = list[a];

	//원래 배열에 저장
	for (a = left; a <= right; a++)
		list[a] = tempNum[a];
}