알고리즘 이론 5강. 병합 정렬(Merge Sort)

 

[병합 정렬]

: n 크기의 데이터를 n/2씩 나누어 크기 1의 부분 집합으로 나눈뒤, 두 부분집합간 병합해나가는 알고리즘.

병합 정렬 예시(위키백과)

- 분할과 정복(divide & conquer) approach

: 문제를 여러개의 부문제로 나눈다(Divide)

: 부문제를 재귀적으로 해결해서 정복(Conquer)

: 해결된 부문제를 결합해 원래 문제로 만든다(Combine)

 

 

[병합 정렬 의사코드]

MERGE-SORT(A,p,r):   if p < r     q = floor[(p+r)/2     MERGE-SORT(A,p,q)    //분할     MERGE-SORT(A,q,r)    //분할     MERGE(A,p,q,r)         //병합   MERGE(A,p,q,r):   n1 = q-p+1   n2 = r-q   배열 L, R생성  L[1:n1+1], R[1:n2+1]    //2차 정렬 알고리즘    for i = 1~n1:     L[i] = A[p+i-1]   for j = 1~n2:     R[i] = A[q+j]   ... 생략

 

 

[2차 정렬 알고리즘]

: 두개의 정렬된 부분배열을 병합하는 알고리즘이다.

: 두 부분배열을 합친 크기와 같은 배열을 새로 만든다. : 두 부분배열의 맨 앞 요소끼리 비교해 더 작은(큰) 값을 꺼내 새로만든 배열에 넣는다. : 값이 빠진 배열의 다음 비교대상은 그 다음 값이다 : 두 부분배열중 한 부분배열의 값이 전부 빠지면, 새로운 배열에 남은 부분배열값을 붙인다.

 

[분할정복의 시간복잡도]

: 분할정복 알고리즘은 기본적으로 3단계로 구성된다 (분할, 정복, 결합)

 

 

[병합정렬의 시간복잡도]

• 분할 : 배열의 분할 위치(중간) 계산 => 시간복잡도 : Θ(1)
• 정복 : 분할된 부분배열들 재귀적으로 해결(정렬) => 수행시간 : 2T(n/2)

ex) n=2 -> 부분 집합 크기 : 1  => 수행시간 : 2T(1) ex) n=4 -> 부분 집합 2 2개 -> 부분집합 1 4개 => 수행시간 : 2T(2)

• 결합 : 두 부분집합 병합 => 시간복잡도 : Θ(n)

# 병합정렬 점화식

  : 위 세작업 수행시간 합침

T(n) = Θ(1)                 if n=1          2T(n/2)+Θ(n)      if n>1

=> 시간복잡도 : Θ(nlogn)

# 병합정렬 점화식 시간복잡도 도출(재귀트리방법)

배열의 크기가 cn이라고 해보자.

cn의 배열의 크기는 분할과정을 거치며 cn/2, cn/4 ... c 으로 분할한다.

 

다음으로, 트리의 각 레벨에서 비용을 본다.

최상 레벨에선 cn이 한개라 비용 : cn

다음 레벨에선 cn/2이 2개라 비용 : cn

...

결국 모든 레벨에서 각 비용이 cn임을 알 수 있다.

 

그리고, 배열의 크기가 cn인 트리가 c까지 분할될때 총 레벨수는 logn + 1의 크기이다.

  ex) cn = 8 이면 트리 레벨 : 4 (8 -44 -2222- 1111111) = log8 + 1

 

마지막으로, 점화식의 총 비용을 알아보려면 모든 레벨의 비용을 더하면 된다.

  최상 레벨(레벨 0) 에서 cn 한개 -> 0 * cn

  레벨 1 에서 cn/2 2개 -> 1 * cn

  ...

  결국 (logn + 1) * cn 이라는 일반식을 도출할 수 있다.

 

결론) 점화식의 총 비용 : cn(logn + 1) 이다.

여기서 시간복잡도로 표현 하기위해 낮은 차수와 상수(cn, c)를 제거하면 시간복잡도 O(nlogn)이 도출된다.