[C] 백준 2750번: 수 정렬하기(합병 정렬)

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

void printNumbers(int* nums, int length) {
	for (int i = 0; i < length; i++) printf("%d\n", nums[i]);
}

void doMerge(int* nums, int left, int right) {
	int mid = (left + right) / 2;
	int length = right - left;

	// Set newNums
	int cp = 0;
	int lp = left;
	int rp = mid + 1;

	int* newNums = malloc(sizeof(int) * (length + 1));
	while (lp <= mid && rp <= right) {
		if (nums[lp] <= nums[rp])
			newNums[cp++] = nums[lp++];
		else
			newNums[cp++] = nums[rp++];
	}

	while (lp <= mid)
		newNums[cp++] = nums[lp++];

	while (rp <= right)
		newNums[cp++] = nums[rp++];

	// Deepcopy
	for (int i = left; i < right+1; i++) nums[i] = newNums[i-left];

	// Free used array
	free(newNums);
}

void doMergeSort(int* nums, int left, int right) {
	if (left == right) return;

	int mid = (left + right) / 2;
	doMergeSort(nums, left, mid);
	doMergeSort(nums, mid+1, right);
	
	doMerge(nums, left, right);
}

int main() {
	// Input
	int N;
	scanf("%d", &N);

	int* nums = malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
		scanf("%d", &nums[i]);

	// Solution
	doMergeSort(nums, 0, N - 1);
	printNumbers(nums, N);

	// Free
	free(nums);

	return 0;
}

 

doMergeSort()가 후위 순회와 같은 재귀 구조를 갖고 있으며, 이는 doMerge()를 수행해주는 부분에서는 left~mid, mid+1~right가 각각 정렬되어있다는 것을 암시한다.

doMerge()에서는 mid를 기준으로 분리된 두 섹터가 정렬되어 있는 것을 이용한다. 각 섹터의 앞을 가리키는 인덱스(lp, rp)를 통해 newNums를 정렬된 순서로 채워넣은 뒤, 마지막으로 원래 배열인 nums에 깊은 복사를 해주면 된다.

 

시간 복잡도: O(nlogn)

공간 복잡도: O(N)

안정성: 안정

비고: 제자리 정렬 불가능