Sort
수 정렬하기 2
문제
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
풀이과정
1. 사용한 정렬 알고리즘
처음 구현할 때에는 퀵정렬 을 이용해 구현하였으나 퀵정렬 은 최악의 경우 시간 복잡도가 \(O(n^2)\)으로 백준에 제출하니 시간 초과가 나왔다. 구글링해보니 퀵정렬 은 최악의 경우 시간 복잡도가 좋지 않은 정렬 알고리즘이니 알고리즘 문제를 풀 때에는 웬만하면 사용하지 말라고 한다.
따라서 최악의 경우에도 시간 복잡도가 \(O(nlog_2 n)\)인 병합 정렬 을 통해 문제를 해결하였다.
참고 : 2. 입출력 시
시간이 2초로 제한되어있어 입출력에도 이슈가 발생하리라 생각하여 여러 입출력 함수를 비교해보았다.
-
cin,cout이용 시 : 716ms -
scanf,printf이용 시 : 432ms -
cin.tie(NULL); ios::sync_with_stdio(false);이용 시 : 320ms
cin.tie(NULL); ios::sync_with_stdio(false); 을 이용할 경우 cin, cout를 이용한 것보다 약 2배 빨라진 것을 볼 수 있다.
코드
#include <iostream>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
void merge(int* arr, int* sortedArr, int begin, int middle, int end) {
int sortedInd = begin;
int i = begin;
int j = middle+1;
while (i <= middle && j <= end) {
if (arr[i] < arr[j]) sortedArr[sortedInd] = arr[i++];
else sortedArr[sortedInd] = arr[j++];
sortedInd++;
}
//왼쪽이 오른쪽보다 모두 작은 경우
if (i > middle) {
while (j <= end) {
sortedArr[sortedInd++] = arr[j++];
}
}
//오른쪽이 왼쪽보다 모두 작은 경우
if (j > end) {
while (i <= middle) {
sortedArr[sortedInd++] = arr[i++];
}
}
for (int k = begin; k <= end; k++) arr[k] = sortedArr[k];
}
void mergeSort(int* arr, int* sortedArr, int begin, int end) {
int middle;
if (begin<end) {
middle = (begin + end) / 2;
mergeSort(arr, sortedArr, begin, middle);
mergeSort(arr, sortedArr, middle + 1, end);
merge(arr, sortedArr, begin, middle, end);
}
}
int main() {
cin.tie(NULL);
ios::sync_with_stdio(false);
int n;
cin >> n;
int* arr = new int[n];
for (int i = 0; i < n; i++)
cin >> arr[i];
int* sortedArr = new int[n];
mergeSort(arr, sortedArr, 0, n-1);
for (int i = 0; i < n; i++)
cout << arr[i] << '\n';
return 0;
}
결과
