합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.

Presentation on theme: "합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오."— Presentation transcript:

1 합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: (비내림차순으로) 정렬된 배열 S[1..n] 사용 알고리즘: 합병 정렬 (Merge Sorting) 각 단계별로 두 그룹의 정렬된 데이터를 서로 합쳐서 정렬된 더 큰 그룹으로 만들어 나아가는 정렬

2 합병정렬(Merge Sort) (2/2) 설계 전략
[분할] 배열을 반으로 나누어서 2 개의 부분배열로 분할한다. 각 부분 배열의 크기가 1일 될때까지 계속하여 분할한다. [정복] 가장 작은 수의 인접한 부분 배열 2개로 부터 정렬된 1개의 배열을 얻어낸다. [통합] 정렬된 부분 배열들을 합병하여 하나의 정렬된 배열로 만든다.

3 합병정렬: 알고리즘 void mergesort (int n, keytype[] S){ if (n > 1) {
int h =  n/2 , m = n - h; keytype[] U = new keytype[1..h]; keytype[] V = new keytype[1..m]; copy S[1] through S[h] to U[1] through U[h]; copy S[h+1] through S[n] to V[1] through V[m]; mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } nV, hV, mV, UV, VV, SV nU, hU, mU, UU, VU, SU n, h, m, U, V, S S의 크기가 4일 때… 크기 2 크기 2

4 합병정렬: 합병 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오.
입력: (1) 양의 정수 h, m, (2) 정렬된 배열 U[1..h], V[1..m] (3) 원래의 배열 S[1..h+m] 출력: U와 V에 있는 키들을 하나의 배열에 정렬한 S[1..h+m]

5 합병정렬: 합병 알고리즘 (1/2) [알고리즘 2.3] (P.55)
void merge(int h, int m, keytype[] U, keytype[] V, keytype[] S) { index i, j, k; i = 1; j = 1; k = 1; while (i <= h && j <= m) { if (U[i] < V[j]) { S[k] = U[i]; i++; } else { S[k] = V[j]; j++; } k++; if(i > h)copy V[j] through V[m] to S[k] through S[h+m]; else copy U[i] through U[h] to S[k] through S[h+m]; i=1 j=1 j=2 i=3 j=3 i=5

6 합병정렬: 합병 알고리즘 (2/2) 알고리즘 2.3 설명 각 서브 그룹당 포인터 한 개씩 필요 (i 와 j)
각 포인터가 가리키는 데이터 두 개를 비교하여 더 작은 것을 S 배열에 복사 복사한 것에 대해서는 포인터를 다음으로 움직임 (i++ or j++) 두 그룹 중 하나는 먼저 처리가 완료되어 포인터가 밖으로 나감 (while (i <= h && j <= m) {…}) 남은 그룹의 데이터를 순서대로 S 배열의 남은 저장공간으로 그대로 복사 (while 절 이후…)

7 합병정렬: 최악의 경우 시간 복잡도 (1/3) 최악의 경우 [알고리즘 2.3]의 시간 복잡도 분석
단위연산: U[i]와 V[j]의 비교 입력크기: 2개의 입력 배열에 각각 들어 있는 항목의 개수: h, m 분석: i = h이고, j = m인 상태로 루프(loop)에서 빠져 나가는 것이 최악의 경우임 이때, 단위연산 의 실행 횟수는 h + m – 1 이다. 따라서, 최악의 경우 합병하는 시간복잡도는 W(h, m) = h + m – 1

8 합병정렬: 최악의 경우 시간 복잡도 (2/3) 최악의 경우 [알고리즘 2.2]의 시간 복잡도 분석
단위연산: merge() 함수 입력크기: 배열 S에 들어 있는 항목의 개수 n(=h+m) 분석 1): 최악의 경우 수행시간은 W(n) = W(h) + W(m) + h + m – 1 이 된다. W(h)는 U를 정렬하는데 걸리는 시간 W(m)은 V를 정렬하는데 걸리는 시간, h + m – 1 은 합병하는데 걸리는 시간 정수 n을 2k(k  1)이라고 가정하면, h = m = n/2 이 된다.

9 합병정렬: 최악의 경우 시간 복잡도 (2/3) (p.556)

10 The Master Theorem (1/4) Proof of the theorem is …. omitted.
[부록 B]의 p.564, 정리 B.5 Consider a function f(n) that, for all n=bk for all kZ+, satisfies the recurrence relation: (n=bk 일 때, 다음 점화 관계가 성립하면) f(n) = af(n/b) + cnd with real a≥1, integer b>1, real c>0, d≥0. Then: Proof of the theorem is …. omitted.

11 The Master Theorem (2/4)

12 The Master Theorem (3/4)

13 The Master Theorem (4/4)

14 합병정렬: 최악의 경우 시간 복잡도 (3/3)

15 [부록 B] P.562

16 [부록 B] P.562

17 [부록 B] P.562

18 합병정렬: 공간 복잡도 (1/3) 그러면 합병정렬 알고리즘은 얼마만큼의 추가적인 저장장소가 필요할까?
함수 mergesort를 호출할 때마다 크기가 S의 절반이 되는 U, V가 추가로 필요. 함수 merge에서는 U와 V가 주소로 전달이 되어 그냥 사용되므로 추가적인 저장장소를 만들지 않는다. 따라서, mergesort를 재귀호출할 때마다 얼마만큼의 추가적인 저장장소가 만들어져야 하는지를 계산해 보면 된다. 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이 된다. 다음 재귀 호출에는 n/2, 그 다음에는 n/4 등으로 추가적인 저장장소가 필요하다. 이들 저장장소의 크기를 합하면, 이 된다. 이 분석이 맞는 분석일까?...

19 합병정렬: 공간 복잡도 (2/3) n개 n개 lgn +1 번 n개 n개 = n(lgn +1) 의 저장장소 필요

20 합병정렬: 공간 복잡도 (3/3)

21 합병정렬: 공간 복잡도 향상 알고리즘 (1/4) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
입력: (1) 크기가 n인 배열 S[1..n]  전역적으로 정의 (2) low - 배열의 첫번째 인덱스, high – 배열의 마지막 인덱스 출력: (비내림차순으로) 정렬된 배열 S[1..n] void mergesort2 (index low, index high){ index mid; if (low < high) { mid = (low + high) / 2; mergesort2(low, mid); mergesort2(mid+1, high); merge2(low, mid, high); } ... mergesort2(1, n);

22 합병정렬: 공간 복잡도 향상 알고리즘 (2/4) mergesort2(1,8) mergesort2(1,4)

23 합병정렬: 공간 복잡도 향상 알고리즘 (3/4) 합병(merge2)
문제: 두 개의 정렬된 부분배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 전역적으로 선언되어 있는 부분 배열 S[low..high] (단, S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료됨) (2) 첨자 low, mid, high 출력: 정렬이 완료된 부분배열 S[low..high]

24 합병정렬: 공간 복잡도 향상 알고리즘 (4/4) void merge2(index low, index mid, index high){ index i, j, k; keytype[] U = new keytype[low..high]; i = low; j = mid + 1; k = low; while (i <= mid && j <= high) { if (S[i] < S[j]) { U[k] = S[i]; i++; } else { U[k] = S[j]; j++; } k++; if(i > mid) copy S[j] through S[high] to U[k] through U[high]; else copy S[i] through S[mid] to U[k] through U[high]; copy U[low] through U[high] to S[low] through S[high]; 이 알고리즘이 정말 공간 복잡도를 향상 시키는가?

25 합병정렬: 공간 복잡도 향상 알고리즘 (4/4) keytype[] U = new keytype[1..n];
void main() { … mergesort2(1,n) … } void mergesort2 (index low, index high){ … merge2(…) … } void merge2(index low, index mid, index high){ index i, j, k; i = low; j = mid + 1; k = low; while (i <= mid && j <= high) { if (S[i] < S[j]) { U[k] = S[i]; i++; } else { U[k] = S[j]; j++; } k++; if(i > mid) copy S[j] through S[high] to U[k] through U[high]; else copy S[i] through S[mid] to U[k] through U[high]; copy U[low] through U[high] to S[low] through S[high];

26 [실습 3] 합병 정렬 합병 정렬에 대한 [알고리즘 2.2., 2.3]과 제자리정렬(In-place) 기법인 [알고리즘 2.4, 2.5]를 Java 프로그램으로 작성해보자. SortMain.java 를 분석하기 완성되지 않은 다음 네 함수를 작성한다. public static long mergeSort(int n, int[] s) public static void merge(int h, int m, int[] u, int[] v, int[] s) public static void inPlaceMergeSort(int low, int high) public static void inPlaceMerge(int low, int mid, int high) num 값을 키워가며 각 방법에 대한 수행 시간을 비교한다. 단계별로 num 값을 증가시키면서 수행 시간을 비교해보자. 공간 복잡도를 좋게 만드는 것이 수행시간에도 영향을 미치는가? 그 정도는?