분할정복법
- “Divide and Conquer”
- merge sort
- quick sort
- 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할
- 정복 : 각각의 작은 문제를 순환적으로 해결
- 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함
합병정렬 merge sorting
- 데이터가 저장된 배열을 절반으로 나눔
divide - 각각을 순환적으로 정렬
recursively sort - 정렬된 두개의 배열을 합쳐 전체를 정렬
merge- 추가 배열을 이용해 정렬된 두 배열을 합침
- 정렬된 두 배열을 각각 for문을 돌리고, 두 for문의 인덱스에 해당하는 배열의 요소를 비교한 후 더 작은 값을 추가배열의 인덱스에 차례대로 넣는다.
O(nlogn)
- 일반적으로 quick sort와 같은 시간복잡도를 가진다. 그러나, merge sort는 실행시 별도의 공간을 필요로 한다.
Psuedo code
1
2
3
4
5
6
7
8
9
10
11
12
13
mergeSort(A[], p, r) { // A[인덱스 p에서 r까지] 정렬한다
if (p <= r) { // r보다 p가 작을 때만 정렬할 필요가 있다
q = (p + r) / 2; // p, r의 중간지점 계산
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]을 만든다
}
merge 함수 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void merge (int data[], int start, int middle, int end) {
int i = start; // 원본 배열의 첫 번째 인덱스
int j = middle+1; // 원본 배열의 분할된 두 번째 배열의 첫번째 인덱스
int k = start; // 추가 배열의 첫 번째 인덱스
int tmp[data.length()];
while (i <= middle && j <= end) {
if (data[i] <= data[j]) { // 분할된 첫 번째 배열의 요소와 분할된 두 번째 배열의 요소를 비교
tmp[k++] = data[i++];
} else {
tmp[k++] = data[j++];
}
}
// 아래 두 while문은 필연적으로 둘 중 하나만 실행됨
// 위의 while문을 빠져나올 수 있었던 이유가 둘 중 하나만 성립했기 때문
while (i <= middle) {
tmp[k++] = data[i++]; // 앞 배열에 데이터가 남아있을 경우
}
while (j <= end) {
tmp[k++] = data[j++]; // 뒷 배열에 데이터가 남아있을 경우
}
// 정렬된 추가 배열의 데이터를 원본 배열로 모두 옮긴다
for (int i = start; i <= end; i++) {
data[i] = tmp[i];
}
}
시간복잡도
T(n) = 0 (n이 1일 경우) T(n) = T(n/2) + T(n/2) + n (n이 1이 아닐 때) O(nlogn)
합병정렬 구현 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package Algorithm.sort;
public class MergeSortExample {
public static void main(String[] args) {
int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
printArray(arr);
mergeSort(arr);
printArray(arr);
}
private static void mergeSort(int[] arr) {
int[] tmp = new int[arr.length];
mergeSort(arr, tmp, 0, arr.length-1);
}
private static void mergeSort(int[] arr, int[] tmp, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(arr, tmp, start, mid);
mergeSort(arr, tmp, mid+1, end);
merge(arr, tmp, start, mid, end);
}
}
private static void merge(int[] arr, int[] tmp, int start, int mid, int end) {
for (int i = start; i <= end; i++) {
tmp[i] = arr[i];
}
int part1 = start;
int part2 = mid + 1;
int index = start;
while (part1 <= mid && part2 <= end) {
if (tmp[part1] <= tmp[part2]) {
arr[index] = tmp[part1];
part1++;
} else {
arr[index] = tmp[part2];
part2++;
}
index++;
}
for (int i = 0; i <= mid - part1; i++) {
arr[index + i] = tmp[part1 + i];
}
}
private static void printArray(int[] arr) {
for (int data : arr) {
System.out.printf(data + ", ");
}
System.out.println();
}
}
