기수정렬이란
기수정렬(Radix Sort)은 비교 기반 정렬 알고리즘이 아닌 정수나 문자열과 같은 키(key)를 가진 요소들을 정렬하는 데에 사용되는 알고리즘입니다. 기수정렬은 각 요소의 키를 자릿수별로 비교하고, 가장 낮은 자릿수부터 가장 높은 자릿수까지 반복적으로 정렬하여 최종적으로 정렬된 배열을 얻는 방법을 취합니다. 기수정렬은 비교 기반의 정렬 알고리즘이 가지는 시간 복잡도 하한인 O(n log n)보다 빠른 선형 시간 복잡도 O(nk)를 가지며, 이는 k가 상수라면 O(n)으로 표현됩니다. 여기서 n은 배열의 요소(element)의 수이고, k는 각 요소의 키의 최대 길이(자릿수)를 나타냅니다
작동방식
1.가장 낮은 자릿수부터 시작하여 각 요소의 키를 기준으로 정렬합니다. 이를 최하위 자릿수부터 최상위 자릿수까지 반복합니다.
2. 각 자릿수를 기준으로 정렬하기 위해 안정적인 정렬 알고리즘(예: 계수정렬, 버블정렬, 삽입정렬 등)을 사용합니다.
3. 모든 자릿수를 정렬한 후에는 배열이 완전히 정렬됩니다.
예를 들어 245, 123, 981, 564, 743, 77, 8을 기수정렬로 정렬하는 경우
첫 번째 기수 정렬: 최하위 자릿수에 따라 정렬
98 | 1
12 | 3
74 | 3
56 | 4
24 | 5
07 | 7
00 | 8
두 번째 기수 정렬: 두 번째 자릿수에 따라 정렬
0 | 08
1 | 23
7 | 43
2 | 45
5 | 64
0 | 77
9 | 81
세 번째 기수 정렬: 가장 높은 자릿수에 따라 정렬
008
077
123
245
564
743
981
기수정렬의 특징
비교 기반의 정렬 알고리즘이 가지는 비교 연산 없이 자릿수별로 정렬하기 때문에 키의 형태가 숫자나 문자열과 같이 자릿수로 구분될 수 있는 경우에 더 효율적입니다.
안정적인 정렬 알고리즘이라서 동일한 키를 가진 요소들의 상대적인 순서가 유지됩니다.
자릿수의 최대 길이(k)가 보다 작을 때 효율적입니다. k 보다 값이 큰 경우 다른 정렬 알고리즘을 사용하는 것이 더 바람직할 수 있습니다.
부동소수점 등의 특수한 경우에는 적용이 어려울 수 있습니다.
코드
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
# 현재 자릿수(exp)에 따라 각 숫자의 등장 횟수를 세기
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
# count 배열을 누적합 배열로 변경하기
for i in range(1, 10):
count[i] += count[i - 1]
# 원래 배열을 역순으로 순회하여 output 배열에 정렬하기
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
# output 배열을 arr로 복사하기
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
# 입력 배열의 최대값을 찾아 기수 정렬할 횟수를 결정
max_val = max(arr)
exp = 1
while max_val // exp > 0:
counting_sort(arr, exp)
exp *= 10
arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print("정렬 결과:", arr) # [2, 24, 45, 66, 75, 90, 170, 802]기존에 만들어 놓았던 counting sort로 정렬을 하고 싶었는데 자릿수가 다른 것과 dictionary로는 고려해야 할 점이 많아서 리스트로 바꿔서 다시 짰습니다.
그런 counting sort를 활용하여서 radix sort를 짜보았습니다.
마치며
기수정렬은 비교 기반의 정렬 알고리즘보다 더 빠른 시간 복잡도를 가지지만, 자릿수 별로 정렬하는 과정에서 추가적인 공간이 필요할 수 있습니다. 따라서 특정 상황에서 효율적으로 사용할 수 있지만, 모든 상황에서 유용하지는 않습니다.
