Merge Sort
- 주의할 점은 (l,m-1),(m,r) 로 나누면 (k,k+1) => (k,k-1),(k,k+1) 무한루프 되므로 안 됨. (l, m) (m+1,r) 로 나누자
#include <iostream>
using namespace std;
int N, arr[1000000], arr2[1000000];
void mergeSort(int l, int r) {
if(l>=r) return;
int m = (l+r)/2;
// 각 chunk 정렬
mergeSort(l, m);
mergeSort(m+1, r);
// 두 chunk 합치기
int ptr1 = l, ptr2 = m+1, ptr = l;
while(ptr1<=m && ptr2<=r) {
if(arr[ptr1]<arr[ptr2]) arr2[ptr++] = arr[ptr1++];
else arr2[ptr++] = arr[ptr2++];
}
while(ptr1<=m) arr2[ptr++] = arr[ptr1++];
while(ptr2<=r) arr2[ptr++] = arr[ptr2++];
for(int i=l; i<=r; i++) arr[i] = arr2[i];
}
int main() {
cin >> N;
for(int i=0; i<N; i++) cin >> arr[i];
mergeSort(0, N-1);
for(int i=0; i<N; i++) cout << arr[i] << "\n";
}
Heap Sort
- heapify 함수를 사용해 max heap 생성 및 배열 오름차순 정렬
- index 1부터 사용해야 한다 (이진 트리에서 i <-> 2*i, 2*i+1 이 부모자식 관계 되도록 인덱스 조절)
#include <iostream>
using namespace std;
int N, arr[1000001];
void heapify(int head, int end) {
int tmp = arr[head];
int child = head*2;
while(child<=end) {
// 자식 node 중 더 큰 것을 고르고
if(child<end && arr[child]<arr[child+1]) child++;
// 자신보다 크면 switch, 아니면 반복문 탈출
if(arr[child]>tmp) {
arr[child/2] = arr[child];
child *= 2;
} else {
break;
}
}
arr[child/2] = tmp;
}
int main() {
cin >> N;
for(int i=1; i<=N; i++) cin >> arr[i];
// Max Heap 생성
for(int i=N/2; i>=1; i--) heapify(i, N);
// 오름차순 정렬
for(int i=N; i>=2; i--) {
int tmp = arr[1];
arr[1] = arr[i];
arr[i] = tmp;
heapify(1,i-1);
}
for(int i=1; i<=N; i++) {
cout << arr[i] << "\n";
}
}
https://www.acmicpc.net/problem/2751
'BOJ' 카테고리의 다른 글
[C++] 시간 초과 꿀팁, binary search, 벡터 원소 삭제, set 자료형, map 자료형 (0) | 2023.08.15 |
---|---|
[C++] vector 정렬/안정정렬, vector 중복요소 제거, pair 자료형 (0) | 2023.08.11 |
[C++] cin.eof() (0) | 2023.05.05 |
[C++] 에는 없는 split() + trim() 함수 구현 (나중에 재사용하자~) (0) | 2023.05.05 |
[C++] String pass by value / reference 메모 (0) | 2023.05.05 |