BOJ 2751 : 수 정렬하기 2

알고리즘 문제 전체 링크

 

www.acmicpc.net/problem/2751

 

참고

- 머지 소트 Merge Sort

 

여러 정렬 방법이 있겠지만, 여기에서는 merge sort로 풀어보자.

#include <stdio.h>

int N;

int a[1000000 + 50000];
int b[1000000 + 50000];

void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = 0;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end;i++)
		a[i] = b[i - start];

}

void sort(int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1; 
    
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

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

	for (int i = 0; i < N;i++) scanf("%d", &a[i]);

	sort(0, N - 1);

	for (int i = 0; i < N;i++) printf("%d\n", a[i]);

	return 0;
}

 

아래는 merge에서 k = start, 마지막에 a[i] = b[i]로 수정하였다.

#include <stdio.h>

int N;

int a[1000000 + 50000];
int b[1000000 + 50000];

void merge(int start, int end)
{
	int mid, i, j, k;

	mid = (start + end) >> 1;
	i = start;
	j = mid + 1;
	k = start;

	while (i <= mid && j <= end)
	{
		if (a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++];
	}

	while (i <= mid) b[k++] = a[i++];
	while (j <= end) b[k++] = a[j++];

	for (i = start; i <= end; i++) a[i] = b[i];
}

void sort(int start, int end)
{
	int mid;
	if (start >= end) return;

	mid = (start + end) >> 1;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

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

	for (int i = 0; i < N; i++) scanf("%d", &a[i]);

	sort(0, N - 1);

	for (int i = 0; i < N; i++) printf("%d\n", a[i]);

	return 0;
}