자바 [JAVA] - 합병정렬 / 병합정렬 (Merge Sort)
[정렬 알고리즘 모음]
- Merge Sort [합병/병합 정렬]
이 번에 다뤄볼 정렬은 합병(병합) 정렬이다.
아마 대부분 합병, 혹은 병합이라는 단어를 알고있을 것이다. 왜 합병(병합)이라고 할까? 기본적으로 합병정렬은 '문제를 분할하고, 분할한 문제를 정복하여 합치는 과정'이다.
이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다.
맞다. 합병정렬은 기본적으로 '분할 정복' 알고리즘을 기반으로 정렬되는 방식이다.
쉽게 말해 정렬해야 할 리스트가 주어지면 해당 리스트를 분할을 반복하여 최대한 작게 쪼개진 시점에 부분리스트에서 인접한 원소들끼리 비교하여 정렬하는 방식인 것이다.
구체적으로 알아보기에 앞서 미리 언급하자면 합병 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하기 때문에 '제자리 정렬(in-place sort)이 아니다.' 정확히는 제자리 정렬로 구현할 수는 있지만 그 대신 성능을 일부 포기해야하며 매우 신중하게 구현되어야 한다.
합병정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분리스트부터 차례대로 합쳐나가기 때문에 안정정렬(Stable Sort) 알고리즘이기도 하다.
위 말만 듣는다면 이해하기는 어려울 테니 정렬 방법에 대해 구체적으로 알아보도록 하자.
- 정렬 방법
합병 정렬의 전체적인 과정은 이렇다.
1. 주어진 리스트를 절반으로 분할하여 부분리스트로 나눈다. (Divide : 분할)
2. 해당 부분리스트의 길이가 1이 아니라면 1번 과정을 되풀이한다.
3. 인접한 부분리스트끼리 정렬하여 합친다. (Conqure : 정복)
위 3가지 과정에 의해 정렬되는 방식이다.
이를 좀 더 이해하기 쉽게 이미지로 보자면 다음과 같다.
여기서 주의할 점은 합병정렬의 구현이 반드시 2개의 부분리스트로 나누어야 한다는 점은 아니다.
어디까지나 가장 일반적으로 구현되는 방식이 절반으로 나누는 방식일 뿐이다. 보통 위와 같이 두 개의 부분리스트로 나누는 방식을 two-way 방식이라고 하니 참고하시면 좋을 듯 하다.
그러면 일단 두 개씩 나누어 부분리스트를 생성한다는 것은 이해했을 것이다. 문제는 두 부분리스트를 정렬하고 합치는 방식인데, 그리 어렵지 않으니 빠르게 알아보도록 하자.
일단 우리가 이해하고 있어야 할 점은 각각의 부분리스트는 '정렬된 상태'라는 점이다.
두 부분리스트를 합쳐서 정렬할 때 굳이 삽입, 버블 정렬 등을 활용할 필요가 없다는 것이다. 그럼 어떻게 정렬을해? 라고 묻는다면 각 부분리스트의 첫 번째 원소부터 순차적으로 비교만 해주면 된다.
말로는 어려울 수 있으니 다음 이미지를 보자.
이미 각각의 부분리스트는 오름차순으로 정렬되어있기 때문에 앞부분부터 시작하여 하나씩 비교해주며 정렬해주면 된다.
즉 이 부분만 코드로 보자면 다음과 같다.
/**
* 부분리스트는 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 Sort 구현하기
그럼 본격적으로 구현 된 코드를 보자.
[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 방식으로도 구현이 가능하다.
[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 으로 구현하는 것이 좋다.
- 병합 정렬의 장점 및 단점
[장점]
1. 항상 두 부분리스트로 쪼개어 들어가기 때문에 최악의 경우에도 O(NlogN) 으로 유지가 된다.
2. 안정정렬이다.
[단점]
1. 정렬과정에서 추가적인 보조 배열 공간을 사용하기 때문에 메모리 사용량이 많다.
2. 보조 배열에서 원본배열로 복사하는 과정은 매우 많은 시간을 소비하기 때문에 데이터가 많을경우 상대적으로 시간이 많이 소요된다.
위에서 시간 복잡도에 대해 O(NlogN) 으로 유지가 된다고 했다.
왜 그러한 시간복잡도가 나오는지 한 번 같이 알아보도록 하자.
N개의 데이터가 있는 리스트를 1개까지 쪼개어 트리로 나타내게 되면 이진트리(Binary Tree) 형태로 나온다는 것은 우리가 확인 할 수 있다.
N개 노드에 대한 이진트리의 높이(h)는 logN 인 것은 힙정렬에서 다뤘으므로 해당 링크를 참고하시길 바란다.
그러면 비교 및 정렬 과정을 생각해보아야 한다.
우리가 두 개의 서브리스트(배열)을 sorted 배열에 합치는 merge과정을 생각해보자.
이미 두 서브리스트는 정렬된 형태라 앞 원소부터 차례대로 비교하며 안착시키기만 하면 된다. 즉, 아무리 최악의 상황이어도 두 개의 서브리스트 원소 개수만큼의 비교 및 새 배열로 안착시킨다.
그러면 i번 째 레벨에서 노드의 개수가 2i 개이고, 노드의 크기. 한 노드에 들어있는 원소 개수는 N/2i 개다.
이를 곱하면 한 레벨에서 비교작업에 대한 시간 복잡도는 O(2i × N/2i) 이고 이는 곧 O(N)이다.
그리고 O(N)의 비교작업을 트리의 높이인 logN -1 번 수행하므로 다음과 같이 표기할 수 있다.
O(N) × O(logN)
최종적으로 위를 계산하면 O(NlogN) 의 시간복잡도를 갖는 것을 알 수 있다.
- 정리
합병 정렬의 경우 분할정복 알고리즘과 함께 많이 다뤄지는 정렬이다.
특히 이후에 구현해볼 TIm 정렬의 경우 합병정렬과 삽입정렬을 혼합한 방식이므로 이 합병정렬을 잘 이해하고 있으면 도움이 될 것이다.
각 정렬 알고리즘 별 시간 복잡도와 평균 정렬 속도는 다음과 같다.
보면 충분히 merge sort 또한 빠른 것을 볼 수 있다.
특히 간단하게 구현하면서 안정정렬을 하고자 할 때 합병(병합)정렬은 좋은 선택지가 될 수 있다.
이번 합병 정렬의 경우 분할정복 알고리즘을 알고있어야 하기 때문에 만약 이에 대한 기본 지식이 없을 경우 어려울 수 있는 정렬방식이다.
혹여 부족한 부분이 있거나 궁금한 점, 모르거나 이해가 가지 않는 부분이 있다면 언제든 댓글 달아주시면 감사하겠다.
그 외에 필자가 여러 타입들에 대해 구현 한 정렬 알고리즘 소스 코드들을 자세히 보고싶다면 아래 깃허브 repo에 업로드되어있으니 이를 참고하시길 바란다.
https://github.com/kdgyun/Sorting_Algorithm.git
kdgyun/Sorting_Algorithm
Contribute to kdgyun/Sorting_Algorithm development by creating an account on GitHub.
github.com
'알고리즘 > Java' 카테고리의 다른 글
| 자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort) (8) | 2021.08.01 |
|---|---|
| 자바 [JAVA] - 퀵 정렬 (Quick Sort) (29) | 2021.05.19 |
| 자바 [JAVA] - 힙 정렬 (Heap Sort) (30) | 2021.03.14 |
| 자바 [JAVA] - 셸 정렬 (Shell Sort) (18) | 2021.02.18 |
| 자바 [JAVA] - 거품 정렬 (Bubble Sort) (2) | 2021.01.18 |