6 - 8 힙 정렬 & 6 - 9 도수 정렬

힙 정렬

힙의 특성을 이용하여 정렬하는 알고리즘

힙에서 최댓값은 루트에 위치한다.

선택 정렬을 응용한 알고리즘

최댓값인 원소를 선택하는 시간 복잡도는 O(n), 힙 정렬에서 다시 힙으로 만드는 작업의 시간 복잡도는 O(logn)

 

힙

부모의 값이 자식의 값보다 항상 크거나 작다는 조건을 만족하는 완전 이진 트리

두 값의 대소 관계가 일정하면 된다.

부모와 자식관계는 일정하지만 형제 사이의 대소관계는 일정하지 않다.

 

루트를 삭제한 힙의 재구성

힙에서 루트를 꺼냄

루트 위치의 힙의 마지막 원소(가장 하단의 오른쪽에 위치한 원소)를 비어있는 루트자리로 이동

다음 단계에 있는 자식의 크기를 비교하여 부모의 값이 자식의 값보다 항상 커야 한다는 힙의 조건을 만족시키기 위해 더 큰 자식과 위치를 바꾸고 아래로 내려감

이 과정을 반복하여 자식의 값이 작거나 리프의 위치에 도달하면 종료

 

# 퀵 정렬 알고리즘 구현하기

from typing import MutableSequence

def qsort(a: MutableSequence, left : int, right: int) -> None:
    """a[left] ~ a[right]를 퀵 정렬"""
    pl = left   # 왼쪽 커서
    pr = right    # 오른쪽 커서
    x = a[(left + right) // 2]  # 피벗 (가운데 원소)

    while pl <= pr:
        while a[pl] < x : pl += 1
        while a[pr] > x : pr -= 1
        if pl <= pr:
            a[pl], a[pr] = a[pr], a[pl]
            pl += 1
            pr -= 1

    if left < pr : qsort(a, left, pr)
    if pl < right : qsort(a, pl, right)

def quick_sort(a: MutableSequence) -> None:
    """퀵 정렬"""
    qsort(a, 0, len(a)-1)

if __name__ == "__main__":
    print('퀵 정렬을 수행합니다.')
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num   
    
    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    quick_sort(x)   # 배열 x를 퀵 정렬

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

 

 

도수 정렬 = 분포수 세기 정렬

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

.1. 도수 분포표 만들기

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

3.작업용 배열 만들기

 

b[f[a[i]]]=a[i]

for i in range(n-1,-1,-1):

    f[a[i]] -= 1

    b[f[a[i]]]=a[i]

작업용 배열 b에 값을 저장할 때 참조한 배열 f의 원솟값을 1 감소시키는 이유는 같은 값의 원소를 중복으로 처리하지 않기 위한 것이다.

 

4.배열 복사하기

# 도수 정렬 알고리즘 구현

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]}')