병합 정렬, 힙 정렬, 도수 정렬

출처: Do it! 자료구조와 함께 배우는 알고리즘 입문

병합 정렬

두개의 배열을 합쳐 순서대로 정렬한다.

다음과 같이 sorted 함수로 나타낼수도 있다. 

c= list(sorted(a+b))

from typing import Sequence, MutableSequence

def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None:
    """정렬을 마친 배열 a와 b를 병합하여 c에 저장"""
    pa, pb, pc = 0, 0, 0                 # 각 배열의 커서
    na, nb, nc = len(a), len(b), len(c)  # 각 배열의 원소수 

    while pa < na and pb < nb:  # pa와 pb를 비교하여 작은 값을 pc에 저장
        if a[pa] <= b[pb]: # 둘중 작은 값을 c[pc]에 대입
            c[pc] = a[pa]
            pa += 1 
        else:
            c[pc] = b[pb]
            pb += 1
        pc += 1

    while pa < na:              # a에 남은 원소를 복사
        c[pc] = a[pa]
        pa += 1
        pc += 1

    while pb < nb:              # b에 남은 원소를 복사
        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)  # 배열 a와 b를 병합하여 c에 저장

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

병합 정렬 만들기

원소수가 12개가 있을때 , 6개씩 두개 배열로 나눠서 각각 정렬한 뒤 병합하여 배열 정렬을 완료한다.

 

from typing import MutableSequence

def merge_sort(a: MutableSequence) -> None:
    """병합 정렬"""

    def _merge_sort(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 재귀적으로 병합 정렬"""
        if left < right:
            center = (left + right) // 2

            _merge_sort(a, left, center)            # 배열 앞부분을 병합 정렬
            _merge_sort(a, center + 1, right)       # 배열 뒷부분을 병합 정렬
            print(f'a[{left}] ~ a[{center}]: ', a[left:center+1], end=" ")  # 정렬 전 앞부분 출력
            print(f'a[{center+1}] ~ a[{right}]: ', a[center+1:right+1])      # 정렬 전 뒷부분 출력

            p = j = 0
            i = k = left

            while i <= center: #배열 앞부분 a
                 buff[p] = a[i]
                 p += 1
                 i += 1

            while i <= right and j < p: #배열 뒷부분 b
                 if buff[j] <= a[i]:
                     a[k] = buff[j]
                     j += 1
                 else:
                     a[k] = a[i]
                     i += 1
                 k += 1

            while j < p: #남아있는 원소 배열a에 복사  c
                a[k] = buff[j]
                k += 1
                j += 1

            print(f'병합 후: ', a[left:right+1])  # 병합 후 결과 출력

    n = len(a)
    buff = [None] * n           # 작업용 배열을 생성
    _merge_sort(a, 0, n - 1)    # 배열 전체를 병합 정렬
    del buff                    # 작업용 배열을 소멸

배열 앞부분 a는 앞부분을 비어있는 배열 buff에 복사한다.

배열 뒷부분 a[center+1]~a[right]과 buff로 복사한 배열의 앞부분 p개를 병합한 결과를 배열 a에 저장한다.

c는 buff의 나머지 원소를 배열 a에 복사한다. 

배열 병합의 시간 복잡도는 O(n)이다. 데이터 원소수가 n일때 병합 정렬의 단계는 logn만큼 필요하므로 전체 시간 복잡도는  O(n log n)이다.

 

힙 정렬

https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC

가장 위에 있는 원소를 힙의 루트라고 하고, 힙의 루트는 배열의 최댓값이다. 

모든 부모와 자식 관계는 항상 부모의값 >= 자식의 값이 성립해야한다. 

원소 a[i]에서 부모: a[(i-1)//2], 왼쪽 자식: a[i*2+1], 오른쪽 자식 a[i*2+2]

a)힙에서 루트 10을 꺼내고 비어있는 루트 위치에 힙의 마지막 원소인 1을 이동시킨다. 루트는 마지막 인덱스 배열로 보내버린다. 

https://underdog11.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Heapsort-%ED%9E%99%EC%A0%95%EB%A0%AC#google_vignette

b) 1과 큰값을 가진 자식과 위치를 교환하여 가장 아랫부분(leaf)으로 보낸다. 

https://underdog11.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Heapsort-%ED%9E%99%EC%A0%95%EB%A0%AC

힙 정렬 알고리즘

위에서 정리한 알고리즘에 더하여 최댓값 루트인 9를 꺼내서 a[8] 로 이동시키고 힙으로 재정렬 한다. 

n 값은 배열의 원소수, i값은 배열의 마지막 인덱스일때, 정리하면 다음과 같다. 

1) i 값을 n-1로 초기화 한다. 

2) a[0]과 a[i]를 교환한다.

3)  a[0],a[1],...a[i-1]를 힙으로 만든다.

4)  i값을 1씩 감소시켜 0이되면 종료하고, 그렇지 않으면 2로 돌아간다. 

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬"""

    def down_heap(a: MutableSequence, left: int, right: int) -> None:
        """a[left] ~ a[right]를 힙으로 만들기"""
        temp = a[left]      # 루트

        parent = left
        while parent < (right + 1) // 2:
            cl = parent * 2 + 1     # 왼쪽 자식
            cr = cl + 1             # 오른쪽 자식
            child = cr if cr <= right and a[cr] > a[cl] else cl  # 큰 값을 선택합니다.
            if temp >= a[child]:
                break
            a[parent] = a[child]
            parent = child
        a[parent] = temp

    n = len(a)
  	for i in range((n - 1) // 2, -1, -1):   # a[i] ~ a[n-1]을 힙으로 만들기
        down_heap(a, i, n - 1)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]     # 최댓값인 a[0]과 마지막 원소 a[i]를 교환
        down_heap(a, 0, i - 1)      # a[0] ~ a[i-1]을 힙으로 만들기

부모가 right(맨끝 인덱스)+1 //2 보다 작으면, 왼쪽 자식  2x+1 , 오른쪽 자식 2x+2 서로 비교하여 큰값을 받는다.

루트(부모)가 자식값보다 크면 break를 건다.

 

힙 정렬의 시간 복잡도

단순선택 정렬의 시간복잡도는 O(n^2) 이지만 힙 정렬은 원소의 개수만큼 작업을 반복하므로 전체 정렬하는데 걸리는 시간 복잡도는 O(n log n)으로 크게 줄어든다.

도수 정렬

1단계: 도수분포표 만들기

for i in range(n):
  f[a[i]] +=1

a[0] 자리에 5가 있으므로 배열 f의 인덱스 5자리에 1로 갱신한다. 이작업을 a의 맨끝인 a[n-1]까지 반복한다.

https://velog.io/@doforme/6.-%EC%A0%95%EB%A0%AC-%EB%8F%84%EC%88%98

2단계: 누적 도수 분포표 만들기

for i in range(1,max+1):
  f[i] += f[i-1]

두번째 원소부터 바로 앞의 원솟값을 더하는 과정을 나타낸다.

https://velog.io/@doforme/6.-%EC%A0%95%EB%A0%AC-%EB%8F%84%EC%88%98

3단계: 작업용 배열 만들기

for i in range(n-1,-1,-1):
  f[a[i]] -=1
  b[f[a[i]]] = a[i]

a[8]=3, f[3]=5 의 값을 -1하여 b[4]값에 3을 대입한다. 

이런식으로 a[7] = 1, f[1]=2의 값을 b[1]의 값에 1을 넣는다.

https://velog.io/@doforme/6.-%EC%A0%95%EB%A0%AC-%EB%8F%84%EC%88%98

4단계: 배열 복사하기

for문을 이용해 배열b의 모든 원소를 배열 a에 그대로 복사한다.

for i in range(n):
  a[i]= b[i]

도수정렬 알고리즘을 구현하면 다음과 같다. 

from typing import MutableSequence

def fsort(a: MutableSequence, max: int) -> None:
    """도수 정렬(배열 원솟값은 0 이상 max 이하)"""
    n = len(a)           # 정렬할 배열 a
    f = [0] * (max + 1)  # 누적 도수 분포표 배열 f
    b = [0] * n          # 작업용 배열 b

    for i in range(n):              f[a[i]] += 1                     # [1단계]
    for i in range(1, max + 1):     f[i] += f[i - 1]                 # [2단계]
    for i in range(n - 1, -1, -1):  f[a[i]] -= 1; b[f[a[i]]] = a[i]  # [3단계]
    for i in range(n):              a[i] = b[i]                      # [4단계]

def counting_sort(a: MutableSequence) -> None:
    """도수 정렬"""
    fsort(a, max(a))

if __name__ == '__main__':
    print('도수 정렬을 합니다.')
    num = int(input('원소 수를 입력하세요. : '))
    x = [None] * num  # 원소 수가 num인 배열을 생성

    for i in range(num):  # 양수만 입력받음
        while True:
            x[i] = int(input(f'x[{i}] : '))
            if x[i] >= 0: break

    counting_sort(x)  # 배열 x를 도수 정렬

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