1. 기수정렬

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘.

기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

LSD (Least Significant Digit) 방식의 정렬​

가장 작은 자릿수부터 정렬을 진행 (숫자로 치면 일의 자리수부터)
가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다

MSD (Most Significant Digit) 방식의 정렬​

가장 큰 자릿수부터 정렬을 진행
LSD와 비교했을 때 정렬 상태 확인등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다

LSD VS MSD

• LSD의 경우 1600000 과 1을 비교할 때, Digit의 갯수만큼 따져야하는 단점이 있음. 그에 반해 MSD는 마지막 자리수까지 확인해 볼 필요가 없음.
• LSD는 중간에 정렬 결과를 알 수 없음. (예) 10004와 70002의 비교) 반면, MSD는 중간에 중요한 숫자를 알 수 있음. 따라서 시간을 줄일 수 있음.
• LSD는 MSD에 비해서 page fault가 많이 발생하여 느림
• LSD는 자릿수가 정해진 경우 좀 더 빠를 수 있음.

2. 기수정렬 장단점

장점

• 안정성이 있다.
  - 정렬 알고리즘에서 말하는 안정성이란 키-값 쌍을 가진 객체들 중 같은 키를 가진 객체들의 순서가 정렬 이후에도 유지되는 것을 말한다.
• 문자열, 정수 정렬이 가능하다.

단점

• 자릿수가 없는 것은 정렬할 수 없다. (부동 소숫점)
• 중간 결과를 저장할 bucket 공간을 만들기 위한 메모리가 더 필요하다.
• 정수가 양수가 아닌 음수일때는 사용불가

3. 기수정렬 구현

LSD

from collections import deque

def radix_sort(nums):
    buckets = [deque() for _ in range(10)]

    max_val = max(nums)
    Q = deque(nums)
    cur_ten = 1

    while max_val >= cur_ten:
        while Q:
            num = Q.popleft()
            buckets[(num // cur_ten) % 10].append(num)

        for bucket in buckets:
            while bucket:
                Q.append(bucket.popleft())

        cur_ten *= 10

    return list(Q)


print(radix_sort([15, 27, 64, 25, 50, 17, 39, 28]))

시간복잡도

- 시간복잡도는 O(k(n+r))

• k나 r이 입력크기인 n보다 크지않으면, 시간 복잡도는 O(n)

  • for-루프가 k번 반복
    - k는 입력의 최대 자릿수
  • 루프가 1회 수행될 때 n개의 숫자의 i자리 수를 읽으며, r개로 분류하여 개수를 세고, 그 결과에 따라 숫자가 이동하므로 O(n+r) 시간 소요

참고문헌

https://herong.tistory.com/entry/%EA%B8%B0%EC%88%98%EC%A0%95%EB%A0%ACRidix-Sort
https://week-year.tistory.com/206