병합정렬은 코테의 정렬 관련 문제에서 자주 등장한다!
특히 2개의 그룹을 병합하는 원리는 꼭 숙지해야한다.
병합정렬
- Stable Sort : 비교순위가 동일한것에 대해 작업하기 전 순위를 유지하는 것
- 분할 정복 방식을 사용해, 데이터를 분할하고 분할한 집합을 정렬하며 합치는 알고리즘
특징
- 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 '제자리 정렬(in-place sort)이 아니다.' 정확히는 제자리 정렬로 구현할 수는 있지만 그 대신 성능을 일부 포기해야하며 매우 신중하게 구현되어야 한다.
- 합병정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분리스트부터 차례대로 합쳐나가기 때문에 안정정렬(Stable Sort) 알고리즘이기도 하다.
<단점>
- 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
- 제자리 정렬(in-place sorting)이 아니다.
- 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다.
<장점>
- 안정적인 정렬 방법
- 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
- 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
- 제자리 정렬(in-place sorting)로 구현할 수 있다.
- 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.
분할 정복(divide and conquer) 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
- 대개 순환 호출을 이용하여 구현한다.
<과정>
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.
2. 그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 해당 부분리스트의 길이가 1이 아니라면 2번 과정을 되풀이한다.
4. 인접한 부분리스트끼리 정렬하여 합친다.
여기서 주의할 점은 합병정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다.
어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다.
보통 위와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라고 하니 참고하시면 좋을 듯 하다.
2개의 그룹을 병합하는 과정
추가적인 리스트가 필요하다.
각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다.
합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계 이다.
일단 우리가 이해하고 있어야 할 점은 각각의 부분리스트는 '정렬된 상태'라는 점이다.
두 부분리스트를 합쳐서 정렬할 때 굳이 삽입, 버블 정렬 등을 활용할 필요가 없다는 것이다. 그럼 어떻게 정렬을해? 라고 묻는다면 각 부분리스트의 첫 번째 원소부터 순차적으로 비교만 해주면 된다.
투 포인터 개념을 사용하여 왼쪽, 오른쪽 그룹 병합
왼쪽 포인터와 오른쪽 포인터의 값을 비교하여 작은 값을 결과 배열에 추가하고, 추가된 값의 포인터를 오른쪽으로 1칸 이동
- 2개의 리스트의 값들을 처음부터 하나씩 비교하여 두 개의 리스트의 값 중에서 더 작은 값을 새로운 리스트(sorted)로 옮긴다.
- 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이한다.
- 만약 둘 중에서 하나의 리스트가 먼저 끝나게 되면 나머지 리스트의 값들을 전부 새로운 리스트(sorted)로 복사한다.
- 새로운 리스트(sorted)를 원래의 리스트(list)로 옮긴다.
이미 각각의 부분리스트는 오름차순으로 정렬되어있기 때문에 앞부분부터 시작하여 하나씩 비교해주며 정렬해주면 된다.
이 부분만 코드로보면 다음과 같다.
/**
* 부분리스트는 a배열의 left ~ right 까지이다.
*
* @param a 정렬할 배열
* @param left 배열의 시작점
* @param mid 배열의 중간점
* @param right 배열의 끝 점
*/
private static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분리스트 시작점
int r = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = left; // 채워넣을 배열의 인덱스
while(l <= mid && r <= right) {
/*
* 왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
*/
if(a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/*
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
*/
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* = 오른쪽 부분리스트 원소가 아직 남아있을 경우
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
if(l > mid) {
while(r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* = 왼쪽 부분리스트 원소가 아직 남아있을 경우
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
else {
while(l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/*
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
*/
for(int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}시간복잡도
O(NlogN)
(이미지는 분할단계에서는 비교,이동연산이 수행되지않으므로 합병단계라고 생각해주면 될 것 같다.)
N개의 데이터가 있는 리스트를 1개까지 쪼개어 트리로 나타내게 되면 이진트리(Binary Tree) 형태로 나온다는 것은 우리가 확인 할 수 있다.
N개 노드에 대한 이진트리의 높이(h)는 logN이다.
그러면 비교 및 정렬 과정을 생각해보아야 한다.
우리가 두 개의 서브리스트(배열)을 sorted 배열에 합치는 merge과정을 생각해보자.
이미 두 서브리스트는 정렬된 형태라 앞 원소부터 차례대로 비교하며 안착시키기만 하면 된다.
즉, 아무리 최악의 상황이어도 두 개의 서브리스트 원소 개수만큼의 비교 및 새 배열로 안착시킨다.
(사실 비교자체는 '원소의 개수-1'번 만큼한다)
그러면 i번 째 레벨에서 노드의 개수가 2^i 개이고, 노드의 크기. 한 노드에 들어있는 원소 개수는 N/2^i 개다.
이를 곱하면 한 레벨에서 비교작업에 대한 시간 복잡도는 O(2^i × N/2^i) 이고 이는 곧 O(N)이다.
(원소의 개수를 파악하면 즉 비교횟수를 파악하는거라 할 수 있음. 어차피 빅오표기법에서는 상수는 무시되므로)
그리고 O(N)의 비교작업을 트리의 높이인 logN -1 번 수행하므로 다음과 같이 표기할 수 있다.
O(N) × O(logN)
최종적으로 위를 계산하면 O(NlogN) 의 시간복잡도를 갖는 것을 알 수 있다.
추가적으로 필요한 공간
O(N)
구현
[Top-Down 형식]
public class Merge_Sort {
private static int[] sorted; // 합치는 과정에서 정렬하여 원소를 담을 임시배열
public static void merge_sort(int[] a) {
sorted = new int[a.length];
merge_sort(a, 0, a.length - 1);
sorted = null;
}
// Top-Down 방식 구현
private static void merge_sort(int[] a, int left, int right) {
/*
* left==right 즉, 부분리스트가 1개의 원소만 갖고있는경우
* 더이상 쪼갤 수 없으므로 return한다.
*/
if(left == right) return;
int mid = (left + right) / 2; // 절반 위치
merge_sort(a, left, mid); // 절반 중 왼쪽 부분리스트(left ~ mid)
merge_sort(a, mid + 1, right); // 절반 중 오른쪽 부분리스트(mid+1 ~ right)
merge(a, left, mid, right); // 병합작업
}
/**
* 합칠 부분리스트는 a배열의 left ~ right 까지이다.
*
* @param a 정렬할 배열
* @param left 배열의 시작점
* @param mid 배열의 중간점
* @param right 배열의 끝 점
*/
private static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분리스트 시작점
int r = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = left; // 채워넣을 배열의 인덱스
while(l <= mid && r <= right) {
/*
* 왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
*/
if(a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/*
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
*/
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* = 오른쪽 부분리스트 원소가 아직 남아있을 경우
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
if(l > mid) {
while(r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* = 왼쪽 부분리스트 원소가 아직 남아있을 경우
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
else {
while(l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/*
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
*/
for(int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}기본적으로 위와같이 재귀를 이용하여 풀이한 방식이 가장 이해하기 빠를 것이다.
[Bottom-Up 형식]
public class Merge_Sort {
private static int[] sorted; // 합치는 과정에서 정렬하여 원소를 담을 임시배열
public static void merge_sort(int[] a) {
sorted = new int[a.length];
merge_sort(a, 0, a.length - 1);
sorted = null;
}
// Bottom-Up 방식 구현
private static void merge_sort(int[] a, int left, int right) {
/*
* 1 - 2 - 4 - 8 - ... 식으로 1부터 서브리스트를 나누는 기준을 두 배씩 늘린다.
*/
for(int size = 1; size <= right; size += size) {
/*
* 두 부분리스트을 순서대로 병합해준다.
* 예로들어 현재 부분리스트의 크기가 1(size=1)일 때
* 왼쪽 부분리스트(low ~ mid)와 오른쪽 부분리스트(mid + 1 ~ high)를 생각하면
* 왼쪽 부분리스트는 low = mid = 0 이고,
* 오른쪽 부분리스트는 mid + 1부터 low + (2 * size) - 1 = 1 이 된다.
*
* 이 때 high가 배열의 인덱스를 넘어갈 수 있으므로 right와 둘 중 작은 값이
* 병합되도록 해야한다.
*/
for(int l = 0; l <= right - size; l += (2 * size)) {
int low = l;
int mid = l + size - 1;
int high = Math.min(l + (2 * size) - 1, right);
merge(a, low, mid, high); // 병합작업
}
}
}
/**
* 합칠 부분리스트는 a배열의 left ~ right 까지이다.
*
* @param a 정렬할 배열
* @param left 배열의 시작점
* @param mid 배열의 중간점
* @param right 배열의 끝 점
*/
private static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분리스트 시작점
int r = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = left; // 채워넣을 배열의 인덱스
while(l <= mid && r <= right) {
/*
* 왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
*/
if(a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/*
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
*/
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* = 오른쪽 부분리스트 원소가 아직 남아있을 경우
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
if(l > mid) {
while(r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* = 왼쪽 부분리스트 원소가 아직 남아있을 경우
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
else {
while(l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/*
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
*/
for(int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}merge하는, 즉 병합하는 메소드는 그대로 두고 부분리스트로 나누는 과정만 Bottom-Up 방식으로 변경해주면 된다.
대부분의 경우 정렬 과정은 최대한 재귀는 피하여 구현하는게 일반적이기 때문에 Bottom-Up 으로 구현하는 것이 좋다.
코테에서 주의할 점!
- 합병과정에서 사용되는 임시 배열(코드에서는 'sorted')을 전역변수로 선언하지않고, 지역변수로 merge에 선언해서 사용할 경우 오버헤드가 상당해서 시간초과의 위험이있음
-> 전역변수로 둔다면 한 번 생성해두고 프로그램이 종료되기 전까지는 소멸하지 않고 하나의 동일한 리스트를 공유하지만, 지역변수로 선언한다면 매 번 메소드안에 sorted를 생성하는데 이는 단순히 계산으로 해도 약 2^logN 만큼의 수행이 이루어지기 때문에 리스트 생성해야하는 오버헤드가 커져 시간초과가 발생하게된다.
리스트를 해제하는 과정도 그만큼 많아진다는 것인데, 매우 큰 리스트의 경우 매번 생성 소멸을 반복하게 될 경우 그만큼 가비지 컬렉터가 일을 처리하기 바빠진다. 과도하게 GC가 처리할 일이 많아져 프로세스가 모든 CPU time의 매우 많은 부분을 사용하게 될 경우 GC Overhead Limit Exceeded 에러를 내뱉기도 한다.
그 외
- merge_sort(int[] a)에서
sorted = null;을 해준 이유
: 자바 특정 버전 이후부터는 static 변수도 이제는 GC대상이 되기 때문에 굳이 null처리를 해줄 필요는 없긴 하지만, 데이터의 무결성과 좀 더 안정적인 코드를 작성하기 위해서는 확실하게 필요없는 데이터는 명시적으로 이해하기 쉽게 코드로 작성되는 것이 올바르다.
sorted는 임시배열의 목적인만큼, 정렬 수행과정 중 생성되고, 삭제되는 배열이구나!라고 코드를 보고 이해할 수 있어야 좋은 코드겠다!
참고
https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
https://st-lab.tistory.com/233
