앞에서 분할정복(Divide And Conquer) 방식을 이용한 MergeSort를 알아봤다.
되새겨 보면,
- 정렬한 대상이 되는 수 전체를, 1개 또는 2개의 수로 구성된 작은 블럭들이 될 때까지 나누고,
- 나눠진 블럭들을 소팅하면서,
- 조금씩 옆에 있는 블럭들을 합쳐서(merge), 수 전체가 소팅되게 하는 것
이처럼 구현하다보면 재귀호출(Recursion)을 사용할 수 밖에 없다.
재귀호출이라는 것은, 메서드내에서 다시 자신을 호출하는 것이기에,
- 프로그램이 진행되는 순서를 인간이 머리로 따라가기가 난해하고,
- 메서드가 다 끝나기 전에 다시 메서드 호출이 일어나는 것이기에,
아직 끝나지 않은 메서드에 대한 정보를 Stack에 저장해 두고 메서드를 콜하는 작업이 반복.
그러다 보면, 동시에 호출되는 메서드가 많은 경우에는 Stack Overflow가 발생할 수 도 있다.
재귀호출에는 위와 같은 단점이 있기에, 가능한 재귀호출하지 않는 코드를 짜는 것이 좋다.
MergeSort도 재귀호출을 사용하지 않고 구현할 수 있다.
원래의 배열을 절반씩 나눠가면서 소팅하는 것이 아니고, 작은 블럭부터 시작해서 소팅해가면서 조금씩 합쳐나가는 것.
재귀호출을 사용한 것은, 원래 배열을 작은 블럭으로 나눠가는 것이기에, 위에서 아래쪽으로 쪼게어 간다는 이미지 연상으로, TopDown으로 부르고, 재귀호출을 사용하지 않는 방법은, 이미 나눠졌다고 가정하고, 그 작은 블럭들을 소팅하면서 merge하면 원래의 배열로 올라가는 것이기에, BottomUp방법이라 한다.
- 맨 처음은, 정렬하려는 배열의 값을 2개씩 묶어서 정렬한 후(n이 홀수인 경우, 제일 마지막 블럭은 1개만)
-> BlockSize = 2
- 이 2개 혹은 1개씩 되어 있는 블럭끼리 묶어서 소팅
-> BlockSize = 4
- 다시 4개짜리 블럭을 소팅하면서 머지
-> BlockSize=8
TopDown방법에서 짜 놓은 merge() 함수를 사용하는 것으로 한다면, 다음과 같은 순서로 merge() 메서드가 호출되면 되겠다.
-> merge(int[] src, int s, int m, int e, int[] buf)인데, 이해하기 쉽게 s와 e만 가지고 표현해본다.
BlockSize=2: merge(0,1) merge(2,3) merge(4,5) merge(6,7)
BlockSize=4: merge(0,3) merge(4,7)
BlockSize=8: merge(0,7)
즉, BlockSize를 2의 거듭제곱만큼씩 커지게 하면서,
이에 해당하는 배열의 start와 end를 지정해주면서 merge() 메서드를 호출하면 되겠다.
구현하면 아래와 같이 될 것임.
private void mergeSort_bottomUp(int[] src, int[] buf){
int n=src.length;
int s,m,e;
for(int blockSize=2;blockSize<=n;blockSize = 2 * blockSize){
for(s=0;s<n;s=s+blockSize){
e=s+blockSize-1;
if(e>=n) e=n-1;
m = (e+s) / 2;
merge(src,s,m,e,buf);
System.arraycopy(buf, s, src, s, (e-s)+1);
}
}
}
코드에서 e값이 원래 배열값의 max를 벗어날 수도 있기에, 벗어나지 않도록 조치한 부분도 주의.
if(e>=n) e = n-1;
전체 소스는 다음과 같음.
package divideandconquer;
public class MergeSort_BottomUp {
public static void main(String[] args){
MergeSort_BottomUp mergeSort = new MergeSort_BottomUp();
int[] a = {6,5,3,1,8,7,2,4};
//int[] a = {6,5,3,1,8,7,2,4,9};
println(a);
mergeSort.sort(a);
println(a);
}
private static void println(int[] a){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println("");
}
public MergeSort_BottomUp(){
}
public void sort(int[] src){
int[] buf = new int[src.length];
mergeSort_bottomUp(src,buf);
}
private void mergeSort_bottomUp(int[] src, int[] buf){
int n=src.length;
int s,m,e;
for(int blockSize=2;blockSize<=n;blockSize = 2 * blockSize){
for(s=0;s<n;s=s+blockSize){
e=s+blockSize-1;
if(e>=n) e=n-1;
m = (e+s) / 2;
merge(src,s,m,e,buf);
System.arraycopy(buf, s, src, s, (e-s)+1);
}
}
}
private void merge(int[] a, int s, int m, int e, int[] buf){
//System.out.println("merge("+s+","+m+","+e+")");
int left=s,right=m+1;
for(int k=s;k<=e;k++){
buf[k] = (left<=m && (right>e || a[left]<=a[right] )) ? a[left++] : a[right++];
}
//println(buf);
}
}
-끝-
'알고리즘 > 알고리즘(Java)' 카테고리의 다른 글
| [분할정복]Power a^n (0) | 2015.10.27 |
|---|---|
| [분할정보]Counting Inversions (0) | 2015.10.27 |
| [분할정복]분할정복 개요-MergeSort (0) | 2015.10.26 |
| 25. [다이나믹]효율적인 행렬곱 순서 (0) | 2015.04.26 |
| 24.[다이나믹]조립라인 스케줄링(Assembly Line Scheduling) (0) | 2015.04.25 |