[분할 정복 알고리즘 1] 병합 정렬(Merge Sort)

백준 Z문제(www.acmicpc.net/problem/1074)를 풀다가 분할 정복 개념을 다시 공부해야겠다고 느껴서 공부도 할 겸, 정리도 한번 할겸 이 글을 써봅니다!

 

1. 분할 정복(Divide and Conquer) 알고리즘이란?
2. 병합 정렬이란?
3. 병합 정렬 시간 복잡도

 

1. 분할 정복(Divide and Conquer) 알고리즘이란?

어떤 문제를 재귀적으로 분할, 정복, 그리고 결합하는 3단계의 방법으로 해결하는 기법입니다.

 

1) 분할 (divide) : 원래 문제를 더 작은 단위로 나눈다.

 - 예시) 병합 정렬에서 길이가 8인 원소를 길이가 4인 두개의 리스트로 나누는 단계

2) 정복 (conquer) : 문제의 단위가 해결하기에 충분히 작아졌다면, 종료 조건을 가지고 문제를 해결한다.

 - 예시) 병합 정렬에서 원소를 비교하여 정렬하는 단계

3) 결합 (combine) : 작은 단위에서 해결된 문제들을 합쳐서 상위 문제를 해결한다.

 - 예시) 병합 정렬에서 정렬된 문제 1쌍을 합침으로써, 상위 문제를 해결하는 단계

분할 정복의 개념에 대해서 간단하게 설명해보았는데, 좀 더 이해하기 쉽도록 병합 정렬을 예를들어 보겠습니다.

 

2. 병합 정렬이란?

큰 문제를 작은 문제로 나누고(분할), 정렬한 후(정복), 정렬된 작은 문제들을 결합하여 상위 문제를 풀어나가는 알고리즘입니다. 길이가 7인 배열을 예로 들어 시작해보겠습니다.

출처 : Wikipedia (https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm)

 

먼저 첫번째, 분할 단계입니다.

1) 왼쪽과 오른쪽 배열로 나눠주기 위해 중간 인덱스를 mid = len(arr) // 2로 잡고, 배열의 크기가 1이 될 때까지 계속 반으로 나눠줍니다. (left = mergesort(arr[:mid]) 부분과 right = mergesort(arr[mid:]) 부분)

2) 배열의 크기가 2보다 작다면 원소의 개수가 1개이므로 정렬이 필요없습니다. 따라서, 해당 원소 1개를 바로 return 해줍니다.

def mergesort(arr):
    # 배열의 크기가 0 또는 1일 경우, 정렬할 필요 없으므로 그대로 return
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])  # 분할 (왼쪽 부분)
    right = mergesort(arr[mid:])  # 분할 (오른쪽 부분)
    return merge(left, right)  # 정복 및 결합

 

두번째, 정복 및 결합 단계입니다.

1) 위의 코드에서 원소의 개수가 1인 경우까지 분할이 끝나면, 원소의 개수가 1인 배열을 시작으로 merge 함수가 호출되어 정렬을 하고, 결합을 합니다.

 - return merge([27], [43])  → 정렬 후 결합된 값 = [27, 43]

def merge(left, right):
    sorted = []
    # 임시 배열에 작은 순서대로 정렬하여 삽입하기
    i = 0
    j = 0
    # print(left, right)
    while (i < len(left) and j < len(right)):
        if left[i] <= right[j]:
            sorted.append(left[i])
            i += 1
        else:
            sorted.append(right[j])
            j += 1

    # 남은 원소 삽입하기
    ## 왼쪽 리스트가 모두 삽입되어, 오른쪽 리스트를 모두 삽입하지 못한 경우
    if i == len(left):
        for t in range(j, len(right)):
            sorted.append(right[t])
    ## 오른쪽 리스트가 모두 삽입되어, 왼쪽 리스트를 모두 삽입하지 못한 경우
    if j == len(right):
        for t in range(i, len(left)):
            sorted.append(left[t])

    return sorted

 

합쳐진 코드를 보면 아래와 같습니다.

def merge(left, right):
    sorted = []
    # 임시 배열에 작은 순서대로 정렬하여 삽입하기
    i = 0
    j = 0
    # print(left, right)
    while (i < len(left) and j < len(right)):
        if left[i] <= right[j]:
            sorted.append(left[i])
            i += 1
        else:
            sorted.append(right[j])
            j += 1

    # 남은 원소 삽입하기
    ## 왼쪽 리스트가 모두 삽입되어, 오른쪽 리스트를 모두 삽입하지 못한 경우
    if i == len(left):
        for t in range(j, len(right)):
            sorted.append(right[t])
    ## 오른쪽 리스트가 모두 삽입되어, 왼쪽 리스트를 모두 삽입하지 못한 경우
    if j == len(right):
        for t in range(i, len(left)):
            sorted.append(left[t])

    return sorted

def mergesort(arr):
    # 배열의 크기가 0 또는 1일 경우, 정렬할 필요 없으므로 그대로 return
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])  # 분할 (왼쪽 부분)
    right = mergesort(arr[mid:])  # 분할 (오른쪽 부분)
    return merge(left, right)  # 정복 및 결합

arr = [38, 27, 43, 3, 9, 82, 10]
print(mergesort(arr))

 

위의 Wikipedia사진에서는 처음에 왼쪽 4개, 오른쪽 3개로 나눠서 정렬을 했고, 저는 왼쪽을 3개 오른쪽을 4개로 나눴습니다. 중간값을 어떻게 잡아주느냐에 따라 조금 달라질 수 있는 부분이라는 점만 참고하시면 되겠습니다.

 

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

병합정렬은 O(NlogN)의 시간복잡도를 가집니다.

각 단계에서, 문제의 크기가 N일때 병합에 걸리는 시간은 O(N)입니다.

단계는 총 O(logN)개가 있으므로, 이를 곱해서 O(NlogN)이라는 시간복잡도를 구할 수 있습니다.