알고리즘을 공부하는 교재(Do it! 자료구조와 함께 배우는 알고리즘 입문 자바 편, Bohyoh Shibata 저)에서 구현한 병합 정렬(Merge Sort)의 구현 부분에서 이해가 안됐던 부분과 답을 설명한 글이다.
package chap06;
public class Q16 {
public static int[] buff;
public static void main(String[] args) {
}
static void __mergeSort(int[] a, int left, int right) {
if (left < right) {
int i;
int center = (left + right) / 2;
int p = 0;
int j = 0;
int k = left;
__mergeSort(a, left, center);
__mergeSort(a, center + 1, right);
for (i = left; i <= center; i++)
buff[p++] = a[i];
while (i <= right && j < p) {
if (buff[j] <= a[i])
a[k++] = buff[j++];
else
a[k++] = a[i++];
}
while (j < p)
a[k++] = buff[j++];
}
}
static void mergeSort(int[] a, int n) {
buff = new int[n];
__mergeSort(a, 0, n - 1);
buff = null;
}
}책에서 구현해놓은 병합 정렬이다.
여기서 의문이 하나 들었다. 병합정렬을 앞서 설명하기 위해, 정렬을 각각 마친 두 배열이 있을 때, 두 배열을 병합하여 저장하는 코드를 먼저 학습하였다.
class MergeArray {
static void merge(int[] a, int na, int[] b, int nb, int[] c) {
int pa , pb , pc; //a, b, c의 커서 인덱스를 가리키는 변수
pa = pb = pc = 0;
while (pa < na && pb < nb)
c[pc++] = (a[pa] < b[pb]) ? a[pa++] : b[pb++];
while (pa < na)
c[pc++] = a[pa++];
while (pb < nb)
c[pc++] = b[pb++];
}
}여기서는, 혹여나 a 배열과 b 배열 중 하나를 전부 스캔 후 저장하여 첫 번째 while문을 빠져 나왔을 때를 대비해서, b 배열을 전부 스캔해서 빠져 나왔을 때의 경우(2번째 while문), a 배열을 전부 스캔해서 빠져 나왔을 때의 경우(3번째 while문)을 전부 구현해놓았다.
그런데, __mergeSort() 메소드에서는 while문이 3개가 아니라 2개만 존재한다.
Q: 위 __mergeSort() 메소드에서 배열의 정렬된 앞부분을 복사해놓은 buff를 먼저 전부 스캔 후 저장하여 while문을 빠져나왔을 때, 배열의 뒷부분이 정렬된 a[i] ~ a[right - 1]의 일부가 남아있게 된다. 이 경우의 while문을 왜 구현해놓지 않았나?
A: 먼저, 배열의 뒷부분(center + 1부터 right까지)은 이미 정렬된 상태로 자신의 배열, 즉 a 배열에 저장되어 있다는 걸 이해했는지 확인하자.while (i <= right && j < p) { if (buff[j] <= a[i]) a[k++] = buff[j++]; else a[k++] = a[i++]; }첫 번째 while문인 해당 while문에서 buff 배열을 전부 스캔 및 저장한 뒤 빠져나왔다면, 배열의 뒷부분이 저장된 a[i] ~ a[right - 1]의 아직 스캔 및 저장이 안된 일부분보다 buff 배열의 모든 요소들이 작거나 같다는 의미가 된다. (삼항 연산자의 조건문을 잘 이해해보자.)
그리고, 이미 정렬된 상태로 a 배열에 저장되어 있기 때문에, 질문자 Q의 말대로 a[i] + a[right - 1]의 일부가 남아 있는 채 while문을 빠져나와도 a 배열은 정렬을 마친 상태이다. 따라서, while문을 빠져나온 뒤 남은 a 배열의 정렬된 뒷부분을 다시 a 배열에 저장하는 것은 불필요하다는 것을 확인할 수 있다.
