병합 정렬, 힙 정렬 (파이썬)

 

병합 정렬 merge sort

노이만이 고안한 분할 정복 알고리즘. 퀵 정렬과 반대로 안정 정렬에 속한다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다.

 

과정

i) 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다.

ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.

iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다.

iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

 

장점

- 안정적인 정렬 방법

- 레코드를 linked list로 구성하면, 데이터의 이동은 무시할 수 있을 정도로 작아진다. (퀵 정렬을 포함한 다른 정렬 방법보다 효율적이다.)

 

단점

- 레코드를 배열로 구성하면 임시 배열이 필요하다.

- 레코드들의 크기가 큰 경우에는 이동 횟수가 비례적으로 많아진다.

 

from typing import MutableSequence

def merge_sort(a:MutableSequence):
    """병합정렬"""
    def _merge_sort(a:MutableSequence, left: int, right:int):
        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    

---

힙 정렬 heap sort

 

'부모 노드의 값과 자식 노드의 값의 대소 관계가 계속 일정하다'는 조건을 만족하는 완전 이진 트리.

최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조다. 시간 복잡도는 O(n log n)

 

힙에서 부모와 자식 관계는 일정하지만 형제(sibling) 노드 사이의 대소 관계는 일정하지 않으므로 부분 순서 트리(partial odered tree)라고 한다.

 

힙과 배열의 원소 대응

max haep 삽입

 

i) 힙에 새로운 요소가 들어오면, 힙의 마지막 노드에 이어서 삽입한다.

ii) 대소에 맞게 새로운 노드를 부모 노드들과 교환해서 힙을 구현한다.

 

max heap 삭제

 

i) 루트 노드를 삭제 후 루트 노드의 자리에 힙의 마지막 노드를 가져온다. 

ii) 힙을 재구성한다.