힙 정렬, 도수 정렬

Preface

 

오늘 배운 힙 정렬과 도수 정렬을 끝으로 드디어 정렬 알고리즘을 모두 마쳤다.

 

두 방법 모두 글로 쓰여진 설명은 복잡했지만, 실제 코드는 생각보다 간단하여 쉽게 작성할 수 있었다.

 

다만 힙 정렬은 정렬 과정마다 배열을 힙으로 만들어야 하므로 불필요한 계산이 많음에도 불구하고 사용되는 이유가 무엇인지 이해할 수 없었는데, 

 

여러 블로그를 찾아본 결과 힙 정렬은 전체 배열을 정리하는 것이 아니라 가장 큰 값 몇 개만을 필요로 할 때 사용한다고 한다.

---

요즘 들어 공부를 할 때마다 머리를 복잡하게 하는 한 가지 걱정이 있다.

 

책에 쓰여진 코드를 천천히 분석하며 계산해보면 분명 이해는 할 수 있지만, 막상 나에게 동일한 문제가 주여졌을 때 내가 해당 코드를 작성할 수 있을 거란 확신이 들지 않는다는 것이다.

 

얼마 전 까지만 해도 쓰여진 코드를 이해할 수 있으면 충분하다고 생각했었는데, 시간이 지날 수록 비슷한 알고리즘을 적용하여 나만의 코드를 작성할 수 없으면 책에 있는 지식· 정보를 완전히 습득하고 내 것으로 만든 것이 아니라는 생각이 든다.

 

또 코딩 실력이 늘고 있는 것인지, 그대로 멈춰 있는 것인지도 솔직히 잘 모르겠고 오히려 퇴보하는 것은 아닐까 하는 걱정도 된다.

 

친한 친구, 친구의 지인, 오픈 채팅방 등을 통해 나의 공부 방법에 관한 여러 의견을 듣고 답을 정할 시간이 필요한 것 같다.

---

 

1. 힙 정렬

 

 

- 힙 정렬 : 힙의 특성(최댓값은 루트에 위치)을 이용하여 정렬하는 알고리즘

→ 서로 떨어져 있는 원소를 교환하므로 안정적이지 않다.

 

 

- 힙(heap) : 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진 트리

1) 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. (두 값의 대소 관계가 일정하면 됨)

2) 형제의 대소 관계가 정해져 있지 않으므로 부분 순서 트리라고도 한다.

 

 

- 트리 : 각 원소를 의미하는 노드(node)들이 연결된 계층 구조

 

 

- 루트(root) : 부모가 없는 노드

 

 

- 원소 a[i]의 힙에서 인덱스 사이의 관계

1) 부모 : a[(i - 1) // 2]

2) 왼쪽 자식 : a[i * 2 + 1]

3) 오른쪽 자식 : a[(i * 2 + 2]

 

 

- 힙 정렬 과정

1) 힙에서 최댓값인 루트를 꺼낸다.

2) 루트 이외의 부분을 힙으로 만든다.

① 루트를 꺼낸다.

② 마지막 원소(가장 하단의 오른쪽 원소)를 루트로 이동한다.

③ 루트에서 시작하여 자신보다 값이 큰 자식과 자리를 바꾸고 아래쪽으로 내려가는 작업을 반복한다. 이 때 자식의 값이 작거나 리프에 도달하면 종료한다.

 

 

- 리프(leaf) : 트리에서 자식이 없는 노드

 

 

- 힙 정렬 자세한 과정

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

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

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

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

 

※ 해당 순서를 적용하기 전에 배열을 반드시 힙으로 만들어야 한다.

 

 

- 힙 정렬 코드

from typing import MutableSequence


def heap_sort(a: MutableSequence) -> None:

    def down_heap(a: MutableSequence, left: int, right: int) -> None:
        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):
        down_heap(a, i, n - 1)

    for i in range(n - 1, 0, -1):
        a[0], a[i] = a[i], a[0]
        down_heap(a, 0, i - 1)


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

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

    heap_sort(x)

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

 

 

- heapq 모듈을 사용한 힙 정렬 코드

import heapq
from typing import MutableSequence


def heap_sort(a: MutableSequence) -> None:
    heap = []
    for i in a:
        heapq.heappush(heap, i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)


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

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

    heap_sort(x)

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

 

---

 

2. 도수 정렬

 

 

- 도수 정렬 : 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘

1) 매우 빠르고 효율이 좋지만, 데이터의 최솟값과 최댓값을 알아야 적용할 수 있다.

2) 배열 원소를 순서대로 스캔하므로 안정적이다.

 

 

- 도수 정렬 과정

1) 도수 분포표 만들기

2) 누적 도수 분포표 만들기

3) 작업용 배열 만들기 (맨 끝에서 맨 앞으로 스캔)

4) 배열 복사하기

 

 

- 도수 정렬 코드

from typing import MutableSequence


def fsort(a: MutableSequence, max: int) -> None:
    n = len(a)
    f = [0] * (max + 1)
    b = [0] * n

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


def counting_sort(a: MutableSequence) -> None:
    fsort(a, max(a))


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

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

    counting_sort(x)

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