병합 정렬

Preface

 

오늘은 병합 정렬을 공부했는데, 어제 배운 퀵 정렬과 크게 다른 점이 없는 것 같다.

 

퀵 정렬은 배열을 1개의 원소만이 남을 때 까지 두 그룹으로 나누는 작업을 반복하는데, 병합 정렬 역시  배열을 마지막 원소까지 나눈 후 오름차순으로 병합하는 작업을 반복한다.

 

한 가지 차이점이 있다면 퀵 정렬은 피벗을 중심으로 배열을 나누지만, 병합 정렬은 무작위로 그룹을 반으로 나눈다는 것이다.

 

나는 나누어진 원소들을 병합할 때마다 비교하여 정렬하는 병합 정렬보단 한 번 피벗을 설정한 후 나누면서 정렬을 수행하는 퀵 정렬이 훨씬 효율적이라고 생각한다.

 

마지막으로 본문의 첫 번 째 코드에서 a, b 배열의 남은 원소들을 c에 복사할 때 남은 원소들 중 다른 배열의 마지막 원소보다 작은 배열이 있을 경우 정렬이 틀어질 것 같다는 걱정을 잠시 했지만, 이미 정렬을 마친 배열을 병합하는 것이므로 문제가 없을 것 같다고 생각했다.

---

 

- 병합 정렬 : 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘

→ 서로 이웃한 원소만을 교환하므로 안정적이다.

 

 

- 커서 : 인덱스를 저장한 변수

 

 

- 단순 병합 알고리즘 코드

# 정렬을 마친 두 배열을 병합하기

from typing import Sequence, MutableSequence


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

    while pa < na and pb < nb:
        if a[pa] <= b[pb]:
            c[pc] = a[pa]
            pa += 1
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1

    while pa < na:
        c[pc] = a[pa]
        pa += 1
        pc += 1

    while pb < nb:
        c[pc] = b[pb]
        pb += 1
        pc += 1


if __name__ == '__main__':
    a = [2, 4, 6, 8, 11, 13]
    b = [1, 2, 3, 4, 9, 16, 21]
    c = [None] * (len(a) + len(b))
    print('정렬을 마친 두 배열의 병합을 수행합니다.')

    merge_sorted_list(a, b, c)

    print('배열 a와 b를 병합하여 배열 c에 저장했습니다.')
    print(f'배열 a: {a}')
    print(f'배열 b: {b}')
    print(f'배열 c: {c}')

 

 

- 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))


if __name__ == '__main__':
    print('정렬을 마친 두 배열의 병합을 수행합니다.')
    print('배열 a와 b를 병합하여 배열 c에 저장했습니다.')
    print(f'배열 a: {a}')
    print(f'배열 b: {b}')
    print(f'배열 c: {c}')

 

 

- 병합 정렬 알고리즘 순서

→ 배열의 원소 수가 2개 이상인 경우

1) 배열의 앞부분을 병합 정렬로 정렬

2) 배열의 뒷부분을 병합 정렬로 정렬

3) 배열의 앞부분과 뒷부분을 병합

 

 

- 분할 정복법에 따라 재귀적으로 병합 정렬을 하는 코드

from typing import MutableSequence


def merge_sort(a: MutableSequence) -> None:

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

            _merge_sort(a, left, center)
            _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
    _merge_sort(a, 0, n - 1)
    del buff


if __name__ == '__main__':
    print('병합 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num

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

    merge_sort(x)

    print('오름차순으로 정렬했습니다.')
    for i in range(num):
        print(f'x[{i}] = {x[i]}')