백준 2751 수 정렬하기2 C/C++

수 정렬하기 2 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

2 초

256 MB

207024

59021

40876

30.422%

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5
5
4
3
2
1

예제 출력 1 복사

1
2
3
4
5

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

int main(void)
{
	int n;

	

	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	// 배열 arr의 전체 영역 정렬 
	MergeSort(arr, 0,n-1);

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

	return 0;
}

 

병합정렬 혹은 힙정렬을 이용하는 문제다

병합정렬의 구현은 '윤성우의 열혈 자료구조'를 보고 썼다.

 

힙정렬은 힙에 넣었다 빼면 알아서 정렬이 되는데, 우선 힙을 구현할 수 있으면 힙정렬은 끝난 것이다.

 

그래서 병합정렬로 구현해봤는데, 이것은 divide and conquer이라고 부르는 것 같다.

 

우선 배열을 더이상 쪼갤 수 없을 때까지 나눈다.

 

{2,3,4, 1, 5}라는 배열이 있으면

 

{2},{3},{4},{1},{5}가 될 떄까지 배열을 나누고 다시 이 배열을 하나씩 합친다.

 

아래가 위의 코드 중 배열을 합치는 부분이다.

 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	printf("mergetwoarea: %d %d %d \n", left, mid, right);
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

void MergeSort(int arr[], int left, int right)
{
	int mid;

	if (left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left + right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		printf("mergesortleft: %d %d %d \n", left, mid, right);
		MergeSort(arr, left, mid);
		printf("mergesort right: %d %d %d \n", left, mid, right);
		MergeSort(arr, mid + 1, right);

		
		// 정렬된 두 배열을 병합한다.
		
		MergeTwoArea(arr, left, mid, right);
		
	}
}

int main(void)
{
	int n;

	

	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
	}

	// 배열 arr의 전체 영역 정렬 
	MergeSort(arr, 0,n-1);

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

	return 0;
}

위의 코드를 이제 printf로 찍어보면,

 

mergesortleft: 0 2 4
mergesortleft: 0 1 2
mergesortleft: 0 0 1
mergesort right: 0 0 1
mergetwoarea: 0 0 1
mergesort right: 0 1 2
mergetwoarea: 0 1 2
mergesort right: 0 2 4
mergesortleft: 3 3 4
mergesort right: 3 3 4
mergetwoarea: 3 3 4
mergetwoarea: 0 2 4

 

아래와 같이 나오는데

 

왼쪽이 다 나누어지면 이제 합치기를 시도 한다.

 

처음에는 0번째 인덱스와 1번째 인덱스를 합치는데, 위의 예시라면 2와 3을 비교해서 합친다.

 

 

이제 병합하는 부분만 떼어내서 봐보자.

void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid + 1;
	int i;

	int* sortArr = (int*)malloc(sizeof(int) * (right + 1));
	int sIdx = left;

	while (fIdx <= mid && rIdx <= right)
	{
		if (arr[fIdx] <= arr[rIdx])
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	if (fIdx > mid)
	{
		for (i = rIdx; i <= right; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
	else
	{
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}

	for (i = left; i <= right; i++)
		arr[i] = sortArr[i];

	free(sortArr);
}

1개끼리 합칠 때는 빠르게 끝나지만, 2개 이상을 합칠 경우에 이제 비교를한다.

 

왼쪽에서 온 배열과 오른쪽에서 온 배열이 있다고 가정하자.ㅣ

 

fidx {1, 3} rIdx{2,4}가 있다면

 

1과 2를 비교해서 1이 더 작기 때문에, 동적할당한 배열 sortArr에 1을 넣는다

sortArr={1}

그러면서 왼쪽 배열에 있던 인덱스를 arr[fIdx++]를 해주면, fIdx는 2를 가리킨다.

 

그리고 또 3과 2를 비교하는데 이번에는 2가 더 작기 때문에 sortArr에 삽입하고, rIdx를 ++해준다.

sortArr={1,2}가 되고

fIdx는 3을 가리키며, rIdx는 4를 가리킨다. 또 이 둘을 비교해준다.

 

이렇게하면, sortArr={1,2,3}까지 들어가고, 위의 and조건을 벗어나기 때문에 이 반복문을 종료된다.

이 경우 남은 것을 다시 sorArr에 넣어주기 위해 아래 새로운 for문이 시작한다.

 

이 절차를 재귀적으로 수행하면 병합정렬이 종료된다.