[C++] 백준 2750번: 수 정렬하기

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

 

문제 

---

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

 

 

 

제출 코드

---

#include<iostream>
using namespace std;

int N;
int arr[1000];

void merge(int arr[], int left,int mid, int right) {
	int n1 = mid - left + 1; //왼쪽 배열의 크기
	int n2 = right - mid; //오른쪽 배열의 크기

	//임시 배열 생성
	int* leftArr = new int[n1];
	int* rightArr = new int[n2];


	for (int i = 0; i < n1; i++)
		leftArr[i] = arr[left + i];
	for (int i = 0; i < n2; i++)
		rightArr[i] = arr[mid + 1 + i];

	int i = 0, j = 0, k = left;
	while (i < n1 && j < n2) {
		if (leftArr[i] <= rightArr[j]) {
			arr[k] = leftArr[i];
			i++;
		}
		else {
			arr[k] = rightArr[j];
			j++;
		}
		k++;
	}

	while (i < n1) {
		arr[k] = leftArr[i];
		i++;
		k++;
	}
	while (j < n2) {
		arr[k] = rightArr[j];
		j++;
		k++;
	}

	delete[] leftArr;
	delete[] rightArr;

}

void mergesort(int arr[],int left,int right) {
	if (left < right) {
		int mid = left + (right - left) / 2;

		mergesort(arr, left, mid);
		mergesort(arr, mid + 1, right);

		merge(arr, left, mid, right);
	}
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	mergesort(arr, 0, N - 1);

	for (int i = 0; i < N; i++) {
		cout << arr[i] << endl;
	}
	return 0;
}

 

 

설명

---

시간제한이 2초이므로 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.

버블 정렬 = (1,000,000)^2 > 200,0000,000 -> 부적합

병합 정렬 = 1,000,000log2(1,000,000) = 약 20,000,000 < 200,000,000-> 적합