알고리즘 ] 정렬(Merge Sort)

1. Merge Array

- 합병하면서 차례대로 하나씩 비교하면서 배열을 합치면 O(N)의 복잡도를 갖게 된다.

BOJ 11728번(배열 합치기)

#include <iostream>
#include <string>
using namespace std;

int* mergeArray(int* arrayData1, int len1, int* arrayData2, int len2) { // cur번째 row에 말을 배치할 예정임

	int* result = (int*)malloc(sizeof(int) * (len1 + len2));
	int idx1 = 0;
	int idx2 = 0;

	for (int idx = 0; idx < len1 + len2; idx++)
	{
		if (idx1 >= len1)
		{
			result[idx] = arrayData2[idx2++];
		}
		else if (idx2 >= len2)
		{
			result[idx] = arrayData1[idx1++];
		}
		else
		{
			result[idx] = arrayData1[idx1] < arrayData2[idx2] ? arrayData1[idx1++] : arrayData2[idx2++];
		}
	}

	return result;
}

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

	// 입력(갯수)
	int size1, size2;
	cin >> size1 >> size2;

	// 동적할당
	int* array1 = (int*)malloc(sizeof(int) * size1);
	int* array2 = (int*)malloc(sizeof(int) * size2);

	// 입력(배열1)
	for (int idx = 0; idx < size1; idx++)
	{
		cin >> array1[idx];
	}
	// 입력(배열2)
	for (int idx = 0; idx < size2; idx++)
	{
		cin >> array2[idx];
	}

	// 결과
	int* result = mergeArray(array1, size1, array2, size2);
	for (int idx = 0; idx < size1 + size2; idx++)
	{
		cout << result[idx] << " ";
	}
	return 0;
}	

 

 

2. Merge Sort

- 정렬된 두개의 배열을 하나의 배열로 합치면서 정렬하는 알고리즘의 시간복잡도는 O(N)임을 이용하는 알고리즘

- 하나의 배열을 반복적으로 2쌍으로 나누어 1~2개가 될 때까지 나눈다.

- 나누어진 배열을 병합하면서 정렬한다.

#include <iostream>
#include <string>
using namespace std;

int* merge(int* arrayData1, int len1, int* arrayData2, int len2) { // cur번째 row에 말을 배치할 예정임

	int* result = (int*)malloc(sizeof(int) * (len1 + len2));
	int idx1 = 0;
	int idx2 = 0;

	for (int idx = 0; idx < len1 + len2; idx++)
	{
		if (idx1 >= len1)
		{
			result[idx] = arrayData2[idx2++];
		}
		else if (idx2 >= len2)
		{
			result[idx] = arrayData1[idx1++];
		}
		else
		{
			result[idx] = arrayData1[idx1] < arrayData2[idx2] ? arrayData1[idx1++] : arrayData2[idx2++];
		}
	}
	free(arrayData1);
	free(arrayData2);

	return result;
}

int* mergeSort(int* arrayData, int length) {

	if (length == 1)
	{
		return arrayData;
	}
	else if (length == 2)
	{
		if (arrayData[0] > arrayData[1])
		{
			int tmp = arrayData[0];
			arrayData[0] = arrayData[1];
			arrayData[1] = tmp;
		}
		return arrayData;
	}
	else
	{
		int mid = length / 2;
		int* array1 = (int*)malloc(sizeof(int) * mid);
		int* array2 = (int*)malloc(sizeof(int) * (length-mid));
		for (int idx = 0; idx < mid; idx++)
		{
			array1[idx] = arrayData[idx];
		}
		for (int idx = 0; idx < length - mid; idx++)
		{
			array2[idx] = arrayData[mid + idx];
		}
		int* result1 = mergeSort(array1, mid);
		int* result2 = mergeSort(array2, length - mid);

		return merge(result1, mid, result2, length - mid);
	}
}

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	int* a = (int*)malloc(sizeof(int) * (n));

	for (int i = 0; i < n; i++) cin >> a[i];
	int* result = mergeSort(a, n);
	for (int i = 0; i < n; i++) cout << result[i] << '\n';

	free(a);
	free(result);
	return 0;
}

BOJ 2751번(Merge Sort)

(왜 인지.. 런타임 에러가 발생한다...)

 

[참조]

https://blog.encrypted.gg/734?category=773649

https://thefirstapril.com/2019/08/14/Sorting-Algorithm-Bubble-sort-Implementation/

https://www.journaldev.com/31541/merge-sort-algorithm-java-c-python