백준 알고리즘
[Silver V] 수 정렬하기 2 - 2751
성능 요약
메모리: 20972 KB, 시간: 432 ms
분류
정렬
문제 설명
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use std::io::{stdin, BufRead, BufReader, BufWriter, Write};
fn merge_sort(a: &mut [i32], b: &mut [i32], low: usize, high: usize) {
if high - low < 1 {
return;
}
let mid = (low + high) / 2;
merge_sort(a, b, low, mid);
merge_sort(a, b, mid + 1, high);
let mut i = low;
let mut j = mid + 1;
let mut k = low;
while i <= mid && j <= high {
if a[i] <= a[j] {
b[k] = a[i];
i += 1;
} else {
b[k] = a[j];
j += 1;
}
k += 1;
}
while i <= mid {
b[k] = a[i];
i += 1;
k += 1;
}
while j <= high {
b[k] = a[j];
j += 1;
k += 1;
}
for i in low..=high {
a[i] = b[i];
}
}
fn main() {
let stdin = stdin();
let mut reader = BufReader::new(stdin.lock());
let mut buffer = String::new();
reader.read_line(&mut buffer).unwrap();
let cnt: usize = buffer.trim().parse().unwrap();
let mut arr: Vec<i32> = Vec::with_capacity(cnt);
let mut buf: Vec<i32> = Vec::with_capacity(cnt);
for _ in 0..cnt {
buffer.clear();
reader.read_line(&mut buffer).unwrap();
arr.push(buffer.trim().parse().unwrap());
buf.push(0);
}
merge_sort(&mut arr, &mut buf, 0, cnt - 1);
let stdout = std::io::stdout();
let mut writer = BufWriter::new(stdout.lock());
for x in arr.iter() {
writeln!(writer, "{}", x).unwrap();
}
}
