알고리즘 - 병합 정렬

병합 정렬은 배열을 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다.

 

먼저, 정렬된 배열 a, b를 반복문을 이용한 단순 병합을 해보겠습니다.

이럴 경우 병합하는데 필요한 시간 복잡도는 O(n)입니다.

 

def merge_sorted_list(a, b, c) -> None:
    pa, pb, pc = 0, 0, 0    # 각 배열의 커서
    na, nb, nc = len(a), len(b), len(c)     # 각 배열의 크기

    print(f'배열 a: {a}')
    print(f'배열 b: {b}')
    while pa < na and pb < nb:
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
            print('\nwhile 1')
            print(f'배열 a: {a[pa:]}')
            print(f'배열 b: {b[pb:]}')
            print(f'배열 c: {c}')
        else:
            c[pc] = b[pb]
            pb += 1
            print('\nwhile 1')
            print(f'배열 a: {a[pa:]}')
            print(f'배열 b: {b[pb:]}')
            print(f'배열 c: {c}')
        pc += 1

    while pa < na:
        print('\nwhile 2')
        print(f'배열 a: {a[pa:]}')
        print(f'배열 c: {c}')
        c[pc] = a[pa]
        pa += 1
        pc += 1

    while pb < nb:
        print('\nwhile 3')
        print(f'배열 b: {b[pb:]}')
        print(f'배열 c: {c}')
        c[pc] = b[pb]
        pb += 1
        pc += 1


a = [2, 4, 6, 8, 11, 13]
b = [1, 2, 3, 4, 9, 16, 21]
c = [None] * (len(a) + len(b))

merge_sorted_list(a, b, c)

 

첫 번째 while문은 배열 a,b를 비교해서 더 작은 수를 배열 c에 넣어주는 작업입니다.

두 번째 while문은 배열 a에 남아있는 수들을 배열 c에 넣어주고

세 번째 while문도 배열 b에 남아있는 수들을 배열 c에 넣어주는 것입니다.

 

각 while문에 print를 넣어서 어떻게 돌아가는지 확인할 수있습니다.

 

첫 번째 while문

 

첫 번째 while문

 

출력되는 결과를 보면 계속 배열 a,b를 비교해 더 작은 수를 배열c에 넣는 것을 알 수 있습니다.

 

그리고 배열 a에 남은 데이터가 없기 때문에 while2를 건너뛰고 while3으로 갑니다.

while3

차례대로 16과 21을 넣고 병합이 끝납니다.

병합 결과

 

파이썬 heapq모듈의 merge()함수를 사용하면 정렬된 배열을 빠르게 병합할 수 있습니다.

import heapq
a = [2, 4, 6, 8, 11, 13]
b = [1, 2, 3, 4, 9, 16, 21]
c = list(heapq.merge(a, b))

print(c)

 

---

이제 병합 정렬을 만들어 보겠습니다.

병합 정렬의 시간 복잡도는 O(n log n)이고,

서로 떨어져 있는 원소를 교환하는 것이 아니라서 안정적입니다.

 

def merge_sort(a) -> None:

    def sub_merge_sort(a, left, right) -> None:
        if left < right:
            center = (left + right) // 2

            sub_merge_sort(a, left, center)     # 배열의 앞 부분
            sub_merge_sort(a, center+1, right)  # 배열의 뒷 부분

            p = j = 0
            i = k = left

            while i <= center:
                buff[p] = a[i]
                p += 1
                i += 1

            while i <= right and j < p:
                if buff[j] <= a[i]:
                    a[k] = buff[j]
                    j += 1
                else:
                    a[k] = a[i]
                    i += 1
                k += 1

            while j < p:
                a[k] = buff[j]
                k += 1
                j += 1

    n = len(a)
    buff = [None] * n
    sub_merge_sort(a, 0, n-1)
    del buff


print('병합 정렬')
num = int(input('원소 수 입력: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

merge_sort(x)

print('오름차순 정렬')
print(''.join(str(x)))

 

 

sub_merge_sort함수를 보겠습니다.

원래 배열을 두 그룹으로 나누어 정렬시키는 과정을 재귀적으로 만들었습니다.

 

첫 번째 while문은 배열 앞 부분을 임시 배열 buff에 넣어줍니다.

두 번째 while문은 배열 뒷 부분과 buff에 들어있는 배열의 앞부분을 병합해서 원래 배열a에 저장합니다.

세 번째 while문은 buff에 남아있는 원소를 배열 a에 넣어줍니다.

 

여기서 변수 p는 배열 buff에 들어있는 원소의 개수를 뜻하고

변수 j는 buff의 인덱스라고 생각하시면 됩니다.

변수 k는 배열의 뒷 부분과 buff를 배열 a에 넣어줄 때 사용할 인덱스입니다.

마지막으로 변수 i는 배열 뒷 부분의 인덱스입니다.

 

병합 정렬 결과

 

마지막으로 heapq모듈의 merge()를 사용한 병합 정렬입니다.

 

import heapq


def merge_sort(a) -> None:

    def sub_merge_sort(a, left, right) -> None:
        if left < right:
            center = (left + right) // 2

            sub_merge_sort(a, left, center)
            sub_merge_sort(a, center + 1, right)

            buff = list(heapq.merge(a[left: center+1], a[center + 1: right+1]))

            for i in range(len(buff)):
                a[left + i] = buff[i]

    sub_merge_sort(a, 0, len(a)-1)


print('병합 정렬(heapq.merge를 사용).')
num = int(input('원소 수를 입력: '))
x = [None] * num

for i in range(num):
    x[i] = int(input(f'x[{i}] : '))

merge_sort(x)

print('오름차순으로 정렬했습니다.')
print(''.join(str(x)))

 

buff에 정렬 된 앞, 뒤 배열을 병합시켜 넣어주고

buff에 들어있는 원소를 원래 배열인 a에 저장시켜줍니다.