백준 알고리즘
[Silver V] 수 정렬하기 2 - 2751
성능 요약
메모리: 21028 KB, 시간: 316 ms
분류
정렬
제출 일자
2023년 10월 30일 09:35:27
문제 설명
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
입력
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
출력
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
음악 들으면서 같이 공부해요
Code
- 정렬 중에 빠른편인 합병정렬 이용하여 품
```rs
use std::io::{BufReader,BufRead,BufWriter,Write,stdin,stdout};
fn main(){
let mut reader= BufReader::new(stdin().lock());
let mut writer=BufWriter::new(stdout().lock());
let mut input = String::new();
reader.read_line(&mut input).unwrap();
let n:i32= input.trim().parse().unwrap();
// 카운팅 배열 초기화
let mut arr: Vec
= Vec::with_capacity(n as usize); let mut buf: Vec = Vec::with_capacity(n as usize); //배열에 삽입 for _ in 0..n{ input.clear(); reader.read_line(&mut input).unwrap(); arr.push(input.trim().parse().unwrap()); buf.push(0); } merge_sort(&mut arr, &mut buf, 0, n as usize - 1); for x in arr.iter() { writeln!(writer, "{}", x).unwrap(); } writer.flush().unwrap(); }
//합병정렬 //배열 a를 low와 high 사이에서 합병 정렬 //배열을 반으로 나누어 정렬하고 그 후에 정렬된 하위 배열을 합병하여 전체 배열을 정렬 fn merge_sort(a: &mut [i32], b: &mut [i32], low: usize, high: usize) { //high - low가 1보다 작다면, 즉, 배열의 길이가 1이하면 이미 정렬된 상태이므로 함수를 종료 if high - low < 1 { return; }
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
let mid = (low + high) / 2;
//merge_sort를 재귀적으로 호출하여 각각을 정렬
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;
/*분할 정렬된 list의 합병 */
//i와 j는 각 하위 배열을 순회하기 위한 인덱스를 나타냄
//k는 보조 배열 b의 인덱스를 나타냄
//두 하위 배열을 하나의 정렬된 배열로 합치는데, 두 배열의 원소를 비교하여 작은 원소를 b에 복사
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;
}
//첫 번째 하위 배열의 요소들을 b 배열로 복사
// i는 첫 번째 하위 배열을 나타내는 인덱스
while i <= mid {
b[k] = a[i];
i += 1;
k += 1;
} //두 번째 하위 배열의 요소들을 b 배열로 복사 //j는 두 번째 하위 배열을 나타내는 인덱스
while j <= high {
b[k] = a[j];
j += 1;
k += 1;
}
//배열
//a 배열의 low부터 high까지의 범위를 b 배열의 값으로 업데이트하여 정렬된 배열
for i in low..=high {
a[i] = b[i];
} } ```
