이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 87 번째 글 입니다.
목차
실버5 : 정렬 문제이다.
생각
정렬 문제이다. merge sort(합병 정렬)을 구현해보고자 시도했다.
알고리즘
기본적인 병합 정렬의 알고리즘은 다음과 같다.
위키 백과 - 합병 정렬
좀 더 자세한 설명
partition
나누는 방법은 간단하다. 시작과 끝점을 주고, 반을 자르면서 들어가는 것이다. 가장 작은 단위는 1개의 원소를 가질 때이다. 이 위치에 다다랐을 때 합치는 연산을 수행하면서 거꾸로 올라가면 된다.
merge
합칠 때는, 두 개의 바구니에 담긴 원소들을 비교하면서 새로운 바구니에 차곡차곡 담아두어야 한다. 이 때, 한 바구니의 최댓값이 다른 바구니의 중간 원소보다 작을 경우에 나머지 원소들을 한꺼번에 밀어 넣어주어야 한다는 것을 잊지 말자. 또한 최종 바구니에 다 넣었다면, 다른 바구니들을 비교하는데 있어 정렬된 바구니가 필요하므로 원래 배열에 밀어넣어준다.
Code
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
using namespace std;
int N;
int *a, *temp;
void merge(int start, int end) {
int mid = (start+end)/2;
int i = start, j = mid+1, k = start;
while (i <= mid && j <= end) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
int restLoc = i > mid ? j : i; // 병합중 한쪽 바구니가 끝난 경우 나머지의 위치를 결정해줌
while (k <= end) temp[k++] = a[restLoc++]; // (end-start)개수만큼을 채워야 하니, 나머지들을 넣어줌
for (int i = start; i <= end; i++) a[i] = temp[i]; // temp배열에 넣은 녀석들을 원래 것으로 업데이트 해줌
}
void partition(int start, int end){
if (end <= start) return;
int mid = (start+end)/2;
partition(start, mid);
partition(mid+1, end);
merge(start, end);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
a = new int[N+1];
temp = new int[N];
for (int i = 0; i < N; i++) cin >> a[i];
partition(0, N-1);
for (int i = 0; i < N; i++) cout << a[i] << '\n';
}