티스토리 뷰

알고리즘

Merge Sort(병합 정렬)

llilliiillliill 2017. 12. 11. 20:17

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다.


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);
}
}
view raw Merge Sort.java hosted with ❤ by GitHub


'알고리즘' 카테고리의 다른 글

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
댓글