병합 정렬 (Merge Sort)
기본적으로 합병정렬은 ‘문제를 분할하고, 분할한 문제를 정복하여 합치는 과정’ 이다.
•
분할 정복 (Divide and Conquer) 기반으로 정렬되는 방식
•
쉽게 말해 정렬해야할 리스트가 주어지면, 해당 리스트를 분할을 반복하여 최대한 작게 쪼개진 시점에 부분리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식
•
합병정렬은 데이터를 ‘비교’ 하면서 찾기 때문에, ‘비교 정렬’ 이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 제자리 정렬(in-place sort) 이 아니다
•
정확히는 제자리 정렬로 구현할 수는 있지만, 그 대신 성능을 일부 포기해야하며, 매우 신중하게 구현되어야 한다.
•
합병 정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분리스트부터 차례대로 합쳐 나가기 때문에, 안정정렬(Stable Sort) 알고리즘이기도 하다.
합병 정렬의 과정
1.
주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다 (Divide : 분할)
2.
해당 부분리스트의 길이가 1이 아니라면, 1번 과정을 되풀이한다.
3.
인접한 부분리스트까지 정렬하여 합친다 (Conquer : 정복)
예시)
주의할 점은 합병정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다.
어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다.
보통, 위와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라고 한다.
일단 꼭 알고 있어야 할 점은 각각의 부분리스트는 ‘정렬된 상태’라는 점이다.
두 부분리스트를 합쳐서 정렬할 때 굳이 삽입, 버블 정렬 등을 활용할 필요가 없다는 것!
어떻게 정렬해? 라고 묻는다면, 각 부분리스트의 첫번째 원소부터 순차적으로 비교만 해주면된다.
위와 같이 각각의 부분리스트는 오름차순으로 정렬되어 있기 때문에, 앞부분부터 시작하여 하나씩 비교해주며 정렬해주면 된다.
장점
1.
항상 두 부분리스트로 쪼개어 들어가기 때문에, 최악의 경우에도 O(NlogN)으로 유지가 된다.
2.
안정 정렬이다.
단점
1.
정렬 과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다.
2.
보조 배열에서 원본 배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에, 데이터가 많을 경우 상대적으로 시간이 많이 소요된다.
#include <iostream>
using namespace std;
int N, arr[1000001];
int *arr2;
void merge(int left, int right) {
int mid = (left + right) / 2;
int i = left;
int j = mid+1;
int k = left;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j])
arr2[k++] = arr[i++];
else
arr2[k++] = arr[j++];
}
int tmp = i > mid ? j : i;
while(k <= right) arr2[k++] = arr[tmp++];
for (int i = left; i <= right; i++)
arr[i] = arr2[i];
}
void partition(int left, int right) {
int mid;
if (left < right) {
mid = (left + right) / 2;
partition(left, mid);
partition(mid+1, right);
merge(left, right);
}
}
int main() {
cin >> N;
arr2 = new int[N];
for (int i = 0; i < N; i++) {
cin >> arr[i];
}
partition(0, N-1);
for (int i = 0; i < N; i++) {
cout << arr[i];
}
}
C++
복사