5강. 합병정렬

[ 목차 ]

1. 합병정렬 알고리즘

2. 합병 정렬의 수행시간

3. A divide-and-conquer approach

4. 합병정렬의 Pseudo Code

5. 재귀트리

 

1. 합병정렬 알고리즘

1) 3강의 정렬문제 중 하나

2) 두 개의 이미 정렬된 배열이 주어졌을 때 정렬된 하나의 배열로 합치는 알고리즘

 

2. 합병 정렬의 수행시간

1) 두 개의 정렬된 배열의 길이를 각각 n1, n2 라고 가정

2) 주요 함수 : compare(비교), move(이동)

  1] comparison 횟수 <= movement 횟수

  2] monement 횟수 = n1 + n2

  3] compariton 횟수 + movement 횟수 <= 2(n1 + n2)

  4] 최종

 

3. A divide-and-conquer approach

1) 크기가 커서 풀기 어려운 하나의 문제를 크기가 작아서 풀기 쉬운 여러 개의 문제로 바꾸어 푸는 방법

2) divide : n개의 keys를 두 개의 n/2 keys 로 나눔 

3) conquer : 합병정렬을 사용하여 두 개의 배열을 정렬 

4) combine : 두 개의 정렬된 배열을 하나로 합치는 과정 

 

4. 합병정렬의 Pseudo Code

1) A :  n개의 숫자가 들어있는 배열

2) p : 배열의 첫번째 숫자

3) r : 배열의 마지막 숫자

 

5. 재귀트리