기수정렬이란?
기수 정렬의 전체적인 컨셉은 데이터의 각 자릿수를 낮은 자리수에서부터 가장 큰 자리수까지 올라가면서 정렬을 수행하는 것이다. 이러한 이유로 자릿수가 존재하지 않는 데이터들은 기수정렬로 정렬할 수 없다.
기수정렬의 종류
- LSD(Least Significant Digit)
- 가장 작은 자릿수부터 정렬을 진행 (일의 자리수부터)
- 가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만 코드 구현이 MSD에 비해 간결함
- MSD(Most Significant Digit)
- 가장 큰 자릿수부터 정렬을 진행
- LSD와 비교했을 때 정렬 상태 확인 등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있음
기수정렬의 과정 (LSD)
LSD이므로 일의 자릿수부터 확인해서 숫자를 나타내는 버킷에(현재 정수를 정렬하기에 버킷은 숫자를 나타냄) 일의 자릿수를 확인하며 저장함. (일의 자릿수가 2인 친구는 버킷 2에 전부 몰고, 일의 자릿수가 4인 친구는 버킷 4에 전부 몰아줌)
꺼낼 때에는 먼저 저장된 값부터 꺼내게 됨.
일의 자릿수를 몰아준 다음에는 그 다음 자릿수인 십의 자리를 기준으로 버킷에 저장해줌. (나머지 과정은 위와 동일)
마지막 자릿수인 백의 자릿수를 기준으로 버킷에 저장하고 빼줌.
마지막 자릿수까지 검사했다면 오름차순으로 정렬이 완료됨
from collections import deque
def radix_sort(nums):
# 1. 0부터 9까지의 버킷을 생성
buckets = [deque() for _ in range(10)]
# 2. 주어진 숫자들 중 최댓값을 구함
max_val = max(nums)
# 3. 주어진 숫자들을 큐에 저장
Q = deque(nums)
# 4. 현재 자릿수를 나타내는 변수를 초기화
cur_ten = 1
# 5. 최댓값보다 작거나 같은 자릿수까지 반복하여 정렬
while max_val >= cur_ten:
# 6. 큐에 있는 숫자를 꺼내서 해당하는 버킷에 넣음
while Q:
num = Q.popleft()
buckets[(num // cur_ten) % 10].append(num)
# 7. 버킷에 저장된 숫자들을 큐에 다시 넣음
for bucket in buckets:
while bucket:
Q.append(bucket.popleft())
# 8. 다음 자릿수로 이동
cur_ten *= 10
# 9. 정렬된 숫자들을 리스트로 반환
return list(Q)기수정렬의 과정 (MSD)
MSD이기 때문에 가장 큰 자릿수(이 예시에서는 백의 자릿수)부터 확인함
각 숫자를 나타내는 버킷에 백의 자릿수를 확인하며 저장
꺼낼 때는 먼저 저장된 값부터 꺼내게 됨
STEP2부터는 STEP1 과정으로 인해 분류된 그룹끼리 정렬을 수행함
(134, 122)끼리, (224, 232)끼리
두번째 그룹인 (224, 232) 같은 경우는 자릿수를 비교하지 않아도 이미 정렬이 완료된 상태므로 더이상 정렬 안해도 괜찮음
기수정렬의 특징
- 적용 범위가 제한적임(정수, 알파벳, 특수문자 등 아스키로 표현 가능한 것들)
- 비교 연산이 없음
- 안정 정렬에 속함
- 제자리 정렬이 아니어서 추가적인 메모리가 필요함 (기수만큼의 추가 저장 공간, 버킷이 필요함)
- 값의 비교연산 없이 정렬함
- 정렬하는 숫자 자릿수 K에 따라 O(KN)의 시간 복잡도를 가짐
- 비교 연산이 없기에 데이터 삽입과 추출의 빈도수로 성능을 평가함
- 길이가 가장 긴 자리수를 K, 데이터 개수를 N이라고 할 때, K 자리수까지의 반복과 데이터 N개를 반복해서 정렬하기에 N * K가 됨
- 최악과 최선의 경우 모두 O(KN)
참고
https://soobarkbar.tistory.com/156
https://banjjak1.tistory.com/52
https://jeonyeohun.tistory.com/105
https://hongcoding.tistory.com/187
