[알고리즘 분석] 02 - 2 합병정렬(mergesort)

합병정렬(mergesort)

• 문제: n개의 정수를 비내림차순으로 정렬하시오.
• 입력: 정수 n, 크기가 n인 배열 S[1..n]
• 출력: 비내림차순으로 정렬된 배열 S[1..n]
• 보기: 27, 10, 12, 20, 25, 13, 15, 22

합병(merge)

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

 

시간복잡도 분석

합병 알고리즘의 최악의 경우 시간복잡도 분석

• 단위연산: U[i]와 V[j]의 비교
• 입력크기: 2개의 입력 배열에 각각 들어 있는 항목의 개수: h와 m
• 분석: i = h+1이고, j = m인 상태로 루프(loop)에서 빠져 나가는 때가 최악 의 경우로서(V에 있는 처음 m - 1개의 항목이 S의 앞부분에 위치하고, U 에 있는 h개의 모든 항목이 그 뒤에 위치하는 경우), 이 때 단위연산의 실 행 횟수는 h + m -1이다. 따라서, 최악의 경우 합병하는 시간복잡도는 W(h,m) = h + m -1.
• (예) U: 4 5 6 7 V: 1 2 3 8

합병정렬 알고리즘의 최악의 경우 시간복잡도 분석

• 단위연산: 합병 알고리즘 merge에서 발생하는 비교
• 입력크기: 배열 S에 들어 있는 항목의 개수 n
• 분석: 최악의 경우 수행시간은 W(h,m) = W(h) + W(m) + h + m - 1이 된다. 여기서 W(h)는 U를 정렬하는데 걸리는 시간, W(m)은 V를 정렬하는데 걸리는 시간, 그리고 h + m - 1은 합병하는데 걸리는 시간이다. 정수 n을 2^k , (k ≥ 1)이라고 가정하면, h = n/2, m = n/2 이 된다. 따라서 최악의 경우 재현식은:                                               

W (n)∈Θ(n lg n)

 

 

• n이 2의 승(power)의 형태가 아닌 경우의 재현식

그러나 이 재현식의 정확한 해를 구하기는 복잡하다. 그러나, 앞의 이분검색 알고리즘의 분석에서도 보았듯이, n = 2^k 라고 가정해 서 해를 구하면, 이 재현식의 해와 같은 카테고리의 시간복잡도를 얻게 된 다. 따라서 앞으로 이와 비슷한 재현식의 해를 구할 때, n = 2^k 라고 가정해서 구 해도 점근적으로는 같은 해를 얻게 된다.

 

공간복잡도 분석

• 추가적인 저장장소를 사용하지 않고 정렬하는 알고리즘                                                                            - 제자리정렬(in-place sort) 알고리즘
• 합병정렬 알고리즘은 제자리정렬 알고리즘이 아님. 입력배열 S이외에 U와 V를 추가로 만들어서 사용
• 하단의 재귀호출이 종료될 때까지 상위의 재귀호출이 생성하는 공간이 유 지되어야 함.

• 추가적인 저장장소: mergesort를 재귀호출할 때마다 크기가 S의 반이 되는 U와 V가 추가적으로 필요. (Merge 는 추가적인 저장장소 불필요). 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이 된다. 다음 재귀 호출에는 n/2의 추가적으로 필요한 총 저장장소의 크기는 n + n/2 + n/4 + ...=2n      2n∈Θ(n)
• 추가적으로 필요한 저장장소가 n이 되도록, 즉, 공간복잡도가 n이 되도록 알고리즘을 향상시킬 수 있다(다음 절의 알고리즘). 그러나 합병정렬 알고 리즘이 제자리정렬 알고리즘이 될 수는 없다.

합병정렬 알고리즘의 정렬절차

공간복잡도가 향상된 알고리즘

합병정렬(mergesort)

• 문제: n개의 정수를 비내림차순으로 정렬하시오.
• 입력: 정수 n, 크기가 n인 배열 S[1..n]
• 출력: 비내림차순으로 정렬된 배열 S[1..n]
• 알고리즘:

합병(merge2)

• 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오.
• 입력: (1) 첨자 low, mid, high,                                                                                                                     (2) 부분 배열S[low..high], 여기서 S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료되어 있음.
• 출력: 정렬이 완료된 부분배열 S[1ow..high]