정렬 알고리즘 (fin) - 도수정렬

이번 글은 전 단원과 함꼐 작성하려했지만 너무 길어질 것 같아서 나누어 쓴다.

 

도수정렬은 그동안 배웠던 알고리즘과 확실히 다른 느낌을 띄고있어서 이해하는데 많은 어려움이 있었고 오름/내림차순으로 정렬하는데 대소 구분을 하지 않는다는 점에서 신기했다. 

 

하지만 정렬 알고리즘은 범위가 존재해야한다는 제약이 있기 때문에 사용할 때와 사용하지 못할 때의 구분을 확실히 해야한다.

---

도수 정렬

 

원소의 대소관계를 판단하지 않고 빠르게 정렬하는 알고리즘. 범위 조건이 있을 때 시간 복잡도는 O(n) 이며 매우 빠르다는 장점이 있음

 

처음에는 도수정렬에 대해 이해를 하지 못했는데 유튜버 '동빈나' 님의 강의를 듣고 바로 이해할 수 있게 되었다. 이 글을 읽어보아도 이해가 되질 않는다면 동빈나 님의 유튜브를 보는것도 추천한다.

https://youtu.be/n4kbFRn2z9M

먼저 도수정렬을 하기 위해서는 리스트의 원소에 해당하는 범위의 크기와 같은 배열을 만들어야한다. 예를 들자면 정렬해야하는 리스트의 원소 값이 1부터 5까지인 자연수일 때 b리스트는 5의 크기가 되어야 한다. 

 

도수정렬의 순서를 간단히 설명하자면 아래와 같다. ex) 1부터 5까지의 자연수가 있는 a 리스트를 정렬하고자 한다.

 

1. 정렬하고자 하는 리스트인 a리스트에서 1의 개수를 세어 b리스트 0번 인덱스의 그 수를 넣는다.
2. 이 과정을 5까지 반복하면 b 리스트의 0번부터 4번까지의 원소값은 a 리스트의 1부터 5까지의 개수가 들어간다.
3. b [0]은 a리스트의 1인 값이므로 1을 b [0] 값 만큼 출력한다.

코드의 가독성을 위해 4단계로 나누자면 아래와 같다.

1. 도수 분포표 만들기 
2. 누적 도수 분포표 만들기 (자연수의 개수 구하기)
3. 작업용 배열 만들기 
4. 배열 복사하기

다음은 위의 순서를 기초로 한 코드이다.

def fsort(a, max):
    n = len(a)
    f = [0] * (max + 1)
    b = [0] * n

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

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

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

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

def counting_sort(a):		# 리스트의 최댓값을 범위로 설정
    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]}')