티스토리 뷰
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.
Merge Sort(병합 정렬)
분할 정복법(Merge Sort, Quick Sort)
분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
정복 : 각각의 작은 문제를 순환적으로 해결
합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함
1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우
2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다.
의사코드
Merge Sort(A[], p, r) { // 배열 A[p...r]을 정렬한다.
if(p<r) then {
q <- (p+q)/2; ------------------------------- ①
mergesort(A, p, q); ------------------------- ②
mergesort(A, q+1, r); ----------------------- ③
merge(A, p, q, r); -------------------------- ④
}
}
merge(A[], p, q, r) {
정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 합하여
정렬된 하나의 배열 A[p...r]을 만든다.
}
시간복잡도
T(n) = O(nlogn)
소스 코드(Java)
package Sort; | |
//합병 정렬 알고리즘 구현 | |
public class Merge { | |
public static int[] temp = new int[30]; | |
void mergesort(int left, int right, int[] data) { | |
int mid; | |
if(left < right) { | |
mid = (left+right)/2; | |
mergesort(left, mid, data); | |
mergesort(mid+1, right, data); | |
merge(left, mid, right, data); | |
} | |
} | |
void merge(int left, int mid, int right, int[] data) { | |
int l = left; | |
int m = mid+1; | |
int k = left; | |
while(l<=mid || m<=right) { | |
if(l<=mid && m<=right) { | |
if(data[l] <= data[m]) { | |
temp[k++] = data[l++]; | |
} else { | |
temp[k++] = data[m++]; | |
} | |
} else if(l<=mid && m>right) { | |
temp[k++] = data[l++]; | |
} else { | |
temp[k++] = data[m++]; | |
} | |
} | |
for(int i=left; i<=right; i++) { | |
data[i] = temp[i]; | |
} | |
for(int i=0; i<data.length; i++) { | |
System.out.print(data[i]+" "); | |
} | |
System.out.println(); | |
} | |
public static void main(String[] args) { | |
// TODO Auto-generated method stub | |
int [] data = {4, 54, 2, 8, 63, 7, 55, 56}; | |
// 합병 정렬 전 | |
System.out.println("# 합병 정렬 전"); | |
for(int i=0; i<data.length; i++) { | |
System.out.print(data[i]+" "); | |
} | |
System.out.println(); | |
// 합병 정렬 후 | |
System.out.println("# 합병 정렬 후"); | |
Merge test = new Merge(); | |
int left = 0; | |
int right = data.length-1; | |
test.mergesort(left, right, data); | |
} | |
} |
'알고리즘' 카테고리의 다른 글
Heap Sort(힙 정렬) (1) | 2017.12.12 |
---|---|
Quick Sort(퀵 정렬) (0) | 2017.12.12 |
Insertion Sort(삽입 정렬) (0) | 2017.12.11 |
Bubble Sort(거품 정렬) (0) | 2017.12.11 |
Selection Sort(선택 정렬) (0) | 2017.12.11 |