728x90
Merge Sort 번역하기에 따라 병합 정렬 혹은 합병 정렬이라고 불린다. 분할 정복 알고리즘의 하나로 배열을 잘게 쪼개서 정렬을 하고 이를 합치는 방식이다. 말로 설명하기보다 그림으로 이해하는 것이 더 편하다. 아래와 같은 7size의 배열이 있다고 가정하자. 이를 4size의 배열과 3size의 배열로 나눈다. 다시 4size배열을 2size의 배열 두개로 나누고,... size가 하나가 될때까지 반복한다. 이후 각각을 비교해서 합치면서 정렬된 7size의 배열로 만들어준다.
Merge Sort의 시간 복잡도는 O(nlogn)가 된다.
public class merge {
public static void mergeSort(int[] a,int p,int r) {
int q = (int)Math.floor((double)(p+r)/2); //q는 배열을 반으로 나누기 위한 변수
if(p<r){
mergeSort(a,p,q);//p~q까지 쪼개기 재귀하면서 최종적으로는 1개의 자료값만 남게됨.
mergeSort(a,q+1,r);//위의 연산을 하고난 나머지 반쪽들도 똑같이 처리해줌
merge(a,p,q,r);//분할이 끝난 후에 병합을 해줘야함.
}
}
public static void merge(int[] a, int p, int q, int r){
int[] temp = new int[a.length];//a는 현재 조각난 배열이고 temp는 이름 합쳐주기 위한 배열이다.
int i = p;//왼쪽 배열의 인덱스
int j = q+1;//오른쪽 배열의 인덱스
int index = 0;//temp배열 인덱스
while(i<=q && j<= r){//왼쪽 배열과 오른쪽 배열이 다 남아있는 경우
if(a[i]<=a[j]) temp[index++] = a[i++];//크기 비교후 저장
else temp[index++] = a[j++];
}
while(i<=q)//왼쪽 배열이 남은 경우
temp[index++] = a[i++];
while(j<=r)//오른쪽 배열이 남은 경우
temp[index++] = a[j++];
i = p;
index = 0;
while(i<=r)
a[i++] = temp[index++];//결과를 a배열에 저장
}
public static void main(String[] args) {
int[] a= {8,31,48,73,3,65,20,29,11,15};
mergeSort(a,0,9);
for(int i:a){
System.out.printf("%d ",i);
}
}
}
그림을 보면서 소스 코드를 이해하면 더 쉽게 이해할 수 있다. 마지막으로 랜덤한 숫자 10000개를 정렬하는데 걸리는 시간을 측정해보았다.
0.025초로 삽입 정렬보다도 빠른 속도를 보이고 있다.
728x90
