[백준] 수 정렬하기2 c++

수 정렬하기 2 

 

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

2 초

256 MB

343848

105712

74083

31.312%

문제

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

입력

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

출력

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

---

병합 정렬을 통해 문제를 해결한다.

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

static vector<int> A;
static vector<int> Temp;

void Sort(vector<int>& a, int start, int mid, int end)
{
	int i = start;
	int j = mid + 1;
	int k = 0;

	while (i <= mid && j <= end) //temp에 i와 j를 비교해 작은순으로 값을 넣어준다.
	{
		if (a[i] <= a[j])
		{
			Temp[k] = a[i];
			i++;
			k++;
		}
		else
		{
			Temp[k] = a[j];
			j++;
			k++;
		}
	}

	//둘 중에 더 이상 비교할 수가 없다면 temp에 넣어준다.

	while (i <= mid) 
	{
		Temp[k] = a[i];
		i++;
		k++;
	}

	while (j <= end)
	{
		Temp[k] = a[j];
		j++;
		k++;
	}

	k--;

	while (k >= 0)
	{
		a[start + k] = Temp[k];
		k--;
	}
}

void MergeSort(vector<int>& a, int start, int end)
{
	if (start < end)
	{
		int mid = (start + end) / 2;

		MergeSort(a, start, mid);
		MergeSort(a, mid + 1, end);

		Sort(a, start, mid, end);
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int size = 0;

	cin >> size;

	A = vector<int>(size, 0);
	Temp = vector<int>(size, 0);

	for (int i = 0; i < size; i++)
	{
		cin >> A[i];
	}

	MergeSort(A, 0, size - 1);

	for (int i = 0; i < size; i++)
	{
		cout << A[i] << '\n';
	}
}

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