[CLRS] [2-3] Merge Sort(병합 정렬)

1. Introduction

- 알고리즘은 다양하게 선택가능하다. 

- 예를들어 Insertion Sort는 Incremental method(증분 방법)을 사용한다.

- 이번 챕터에선 분할 정복(divide and conquer) 이라는 설계 방법을 간단하게 다루게 된다. 

- 자세한 방법은 챕터 4때 알아보도록 하자.

 

2. Divide and Conquer(분할 정복)

- 많은 유용한 알고리즘들은 재귀적(recursive) 구조를 가지고 있음.

- 주어진 문제를 해결하기 위해, 이들은 스스로 한번 이상 호출하여 하위문제들을 해결함

- 일반적으로 분할 정복(Divide & Conquer)을 따름

- 문제를 원래 문제와 유사하지만 더 작은 크기의 여러 하위 문제로 나누고, 

- 하위 문제를 재귀적으로 해결한 뒤 이러한 해결책들을 결합하여 원래 문제를 해결함

- 다음과 같이 3가지 Step으로 이루어져 있음

 

Step 1) 분할(Divide)

- 문제를 원래 문제와 유사하지만 더 작게 하위 문제로 나눔

Step 2) 정복(Conquer)

- 하위 문제를 재귀적으로 해결

Step 3) 결합(Combine)

- 하위 문제의 해결책들을 결합하여 원래 문제에 대한 해결책을 만듬

 

3. Merge Sort(병합정렬)

- Merge Sort(병합 정렬)은 분할 정복(Divide and Conquer)방법을 따른다. 

- 전체 배열 A[1:n]에서 시작하여 하위 배열 A[p:r]를 정렬하고 점점 더 작은 하위 배열로 재귀적으로 내려감

- 다음은 Merge Sort가 작동하는 방식을 분할정복(Divide and Conquer)로 나타내보았다.

 

Step 1) 분할(Divide)

- 정렬할 하위 배열 A[p:r]을 두 개의 인접한 하위 배열로 나눈다. (각각의 크기는 절반)

- 이를 위해 A[p:r]의 중간점 q를 계산 (p와 r의 평균을 구하고 반올림)

- 그후 A[p:q] & A[q+1:r]로 하위 배열을 나눠준다.

cf) 배열의 길이가 0 또는 1이면 이미 정렬된 것으로 본다.

 

Step 2) 정복(Conquer)

- 각 하위 배열 A[p:q] & A[q+1:r]을 재귀적으로 Merge Sort(병합 정렬)을 사용해 정렬

 

Step 3) 결합(Combine)

- 두 정렬된 하위 배열  A[p:q] & A[q+1:r] 을 병합하여 다시 A[p:r]로 결합하여 정렬된 결과를 만든다.

 

-그림으로 나타내면 다음과 같다.

 

- 이를 파이썬 코드로 구현 해보자.

def merge_sort(arr,left,right):
    if left>=right:
        return

    mid = (left+right)//2
    merge_sort(arr,left,mid)
    merge_sort(arr,mid+1,right)

    return merge(arr,left,right)
    

def merge(arr,left,right):
    tmp = []

    mid = (left + right) //2
    left_s, right_s = left, mid +1

    while left_s <=mid and right_s <= right:
        if arr[left_s] <= arr[right_s]:
            tmp.append(arr[left_s])
            left_s +=1

        else:
            tmp.append(arr[right_s])
            right_s +=1

    while left_s <=mid:
        tmp.append(arr[left_s])
        left_s+=1

    while right_s <= right:
        tmp.append(arr[right_s])
        right_s +=1


    for i in range(left,right+1):
        arr[i] = tmp[i-left]

    return arr

 

 

3.1. 병합정렬의 시간복잡도

- 즉 O(nlogn) 임을 알 수 있다.

 

4. Exercise

Q1) Merge_sort()를 이용하여 [3,41,52,26,38,57,9,49] 정렬하시오.

def merge_sort(arr,left,right):
    if left>=right:
        return

    mid = (left+right)//2
    merge_sort(arr,left,mid)
    merge_sort(arr,mid+1,right)

    return merge(arr,left,right)
    

def merge(arr,left,right):
    tmp = []

    mid = (left + right) //2
    left_s, right_s = left, mid +1

    while left_s <=mid and right_s <= right:
        if arr[left_s] <= arr[right_s]:
            tmp.append(arr[left_s])
            left_s +=1

        else:
            tmp.append(arr[right_s])
            right_s +=1

    while left_s <=mid:
        tmp.append(arr[left_s])
        left_s+=1

    while right_s <= right:
        tmp.append(arr[right_s])
        right_s +=1


    for i in range(left,right+1):
        arr[i] = tmp[i-left]

    return arr
    
 -------------------------------------------------
 
arr = [3,41,52,26,38,57,9,49] 

merge_sort(arr,0,len(arr)-1)

[3, 9, 26, 38, 41, 49, 52, 57]

 

[Reference]

 

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html