백준 2751 수 정렬하기2 (merge sort)

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 O(N^2)의 시간으로는 해결 할 수 없습니다. 따라서 시간복잡도가 O(NlogN)인 merge sort나 heap sort를 이용하면 되는데 저는 merge_sort를 구현해서 풀어보았습니다. 조만간 sort들도 모두 정리를 한번 해야할 것 같습니다.. merge_sort는 기본적으로 두 배열을 합치는 merge 함수와 분할 하고 다시 합치는 merge_sort 함수로 이루어져 있습니다.

 

#include<iostream>

int arr[1000000];

//두 배열의 합병 
void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left;
	j = mid+1;
	k = left;
	
	//list의 합병 
	while(i<=mid && j<=right) {
		if(list[i]<=list[j])
			arr[k++] = list[i++];
		else
			arr[k++] = list[j++];
	}
	
	// 한쪽 부분에 남은 값들 복사 
	if(i>mid) {
		for(l = j; l <= right; l++)
			arr[k++] = list[l];
	}
	else {
		for(l = i; l <= mid; l++)
			arr[k++] = list[l];
	}
	
	//인자로 온 배열에 값 복사 
	for(l = left; l<=right; l++)
		list[l] = arr[l];
}

//합병 정렬 
void merge_sort(int list[], int left, int right) {
	int mid;
	
	if(left < right) {
		mid = (left+right)/2;
		merge_sort(list, left, mid); //분할 
		merge_sort(list,mid+1, right); //분할 
		merge(list, left,mid,right);
	}
}

int main(void) {
	std::ios_base::sync_with_stdio(false);
	int N;
	std::cin >> N;
	int list[N];
	
	for (int i = 0; i < N; i++)
		std::cin>>list[i];
	
	merge_sort(list, 0, N-1);
	
	for(auto n: list)
		std::cout<<n<<'\n';
		
	return 0;
}