This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define endl '\n' | |
| typedef long long ll; | |
| #define MAXN 1000006 | |
| int arr[MAXN]; | |
| int tmp[MAXN]; | |
| void merge_sort(int arr[], int start, int end) { | |
| int mid = (start + end) / 2; | |
| if (start < mid) { | |
| merge_sort(arr, start, mid); | |
| merge_sort(arr, mid, end); | |
| int p = start, q = mid, r= start; | |
| while (p < mid && q < end) { | |
| if (arr[p] < arr[q]) { | |
| tmp[r++] = arr[p++]; | |
| } | |
| else { | |
| tmp[r++] = arr[q++]; | |
| } | |
| } | |
| while (p < mid) { | |
| tmp[r++] = arr[p++]; | |
| } | |
| while (q < end) { | |
| tmp[r++] = arr[q++]; | |
| } | |
| for (int i = start; i < end; i++) { | |
| arr[i] = tmp[i]; | |
| } | |
| } | |
| } | |
| int main() { | |
| ios_base::sync_with_stdio(false); | |
| cin.tie(NULL); | |
| cout.tie(NULL); | |
| int n; | |
| cin >> n; | |
| for (int i = 0; i < n; i++) { | |
| cin >> arr[i]; | |
| } | |
| merge_sort(arr, 0, n); | |
| for (int i = 0; i < n; i++) { | |
| cout << arr[i] << endl; | |
| } | |
| } |
https://www.acmicpc.net/problem/2751
2751번: 수 정렬하기 2
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
www.acmicpc.net
위 문제의 정답코드이기도 합니다.
코드 복사를 하려면 gist의 우측 하단의 view-raw를 누른 뒤 복사하시면 됩니다.
'알고리즘 & Problem Solving > 레퍼런스코드' 카테고리의 다른 글
| [레퍼런스코드] 유클리드 호제법 최대공약수 구하기(GCD) (2) | 2020.05.15 |
|---|---|
| [레퍼런스코드] 에라토스테네스의 체 (0) | 2020.05.08 |
| [레퍼런스코드] Disjoint Set 코드(DSU / Union-Find 자료구조) (0) | 2020.01.25 |