기수정렬의 개념
기수정렬은 숫자를 자릿수별로 정렬하는 방식으로, 비교 기반의 정렬 알고리즘과는 다른 방식으로 작동합니다. 기수(Radix)는 특정 진수를 나타내는 숫자들을 의미합니다. 예를 들어, 10진수의 기는 0부터 9까지, 2진수의 기는 0과 1입니다. 기수정렬에서는 이러한 자릿수를 이용해 데이터를 정렬합니다.
기수정렬의 핵심은, 숫자를 자릿수 단위로 나누어 가장 낮은 자릿수부터 비교해가며 정렬한다는 점입니다. 한 번에 모든 숫자를 비교하는 것이 아니라, 가장 낮은 자릿수부터 차례대로 정렬하고, 그다음 자릿수를 기준으로 다시 정렬하는 방식을 취합니다. 이 과정을 반복하다 보면 마지막에 정렬된 배열을 얻게 됩니다.
기수정렬의 복잡도
기수정렬의 시간 복잡도는 O(n)입니다. 실제 시간 복잡도는 O(d * n)입니다. 여기서 n은 정렬할 데이터의 개수이고, d는 숫자의 자릿수(길이)를 의미합니다. 따라서 일반적으로 자릿수 d는 고정된 값이기 때문에, 기수정렬의 성능은 O(n)으로 간주됩니다.
이 점에서 기수정렬은 퀵 정렬, 머지 정렬 등 비교 기반 정렬 알고리즘이 최적의 경우 O(n log n)의 복잡도를 가지는 것과 비교하여 더 빠를 수 있습니다. 다만, 기수정렬은 특정 조건에서만 더 효율적이기 때문에 모든 상황에서 최선의 선택은 아닐 수 있습니다.
기수정렬의 특징
기수정렬의 가장 큰 장점 중 하나는 비교 기반 정렬 알고리즘보다 빠를 수 있다는 점입니다. 특히, 데이터의 자릿수가 고정되어 있는 경우, 즉 정렬할 데이터가 한정된 자릿수의 자연수나 문자열인 경우에 매우 효율적입니다. 예를 들어, 계좌번호, 주민등록번호, 전화번호 등 고정된 길이의 데이터에 매우 적합합니다.
기수정렬의 예제
기수정렬(Radix Sort)의 작동 원리는 숫자를 자릿수별로 분류하고, 가장 낮은 자릿수부터 차례대로 정렬하는 방식입니다. 이 알고리즘은 각 자릿수의 값을 비교하여 여러 번 정렬을 수행하며, 최종적으로 숫자들을 완전히 정렬된 상태로 만듭니다. 이제 구체적인 예시를 통해 기수정렬의 작동 방식을 살펴보겠습니다.
- 자릿수별로 정렬: 가장 작은 자릿수(일의 자리)부터 시작해서 정렬을 진행합니다.
- 자리 올림: 그다음, 십의 자리, 백의 자리 등 상위 자릿수로 이동하면서 반복적으로 정렬합니다.
- 모든 자릿수 정렬: 자릿수를 모두 처리하면 최종적으로 완벽하게 정렬된 배열이 나옵니다.
다음과 같은 숫자들을 기수정렬로 정렬해봅시다:
[329, 457, 657, 839, 436, 720, 355]
1. 일의 자리부터 정렬
먼저, 일의 자릿수를 기준으로 정렬합니다. 숫자의 마지막 자리를 보고, 작은 것부터 순서대로 배열합니다.
- 일의 자리 기준: 9, 7, 7, 9, 6, 0, 5
이를 바탕으로 배열을 재정렬하면: [720, 329, 839, 436, 457, 657, 355]
2. 십의 자리 정렬
이번에는 십의 자릿수를 기준으로 다시 정렬합니다. 숫자의 두 번째 자리를 비교하여 작은 것부터 정렬합니다.
- 십의 자리 기준: 2, 2, 3, 3, 5, 5, 5
십의 자릿수를 기준으로 배열을 재정렬하면: [720, 329, 436, 839, 355, 457, 657]
3. 백의 자리 정렬
마지막으로 백의 자릿수를 기준으로 정렬합니다. 이제 숫자의 첫 번째 자리를 보고 정렬합니다.
- 백의 자리 기준: 3, 3, 4, 4, 5, 6, 7
백의 자릿수를 기준으로 배열을 재정렬하면: [329, 355, 436, 457, 657, 720, 839]
모든 자릿수에 대해 정렬이 끝났으므로 최종적으로 배열은 다음과 같이 완벽하게 정렬됩니다.
[329, 355, 436, 457, 657, 720, 839]
기수정렬의 파이썬 코드
def counting_sort(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for i in range(n):
index = arr[i] // exp
count[index % 10] += 1
for i in range(1, 10):
count[i] += count[i - 1]
i = n - 1
while i >= 0:
index = arr[i] // exp
output[count[index % 10] - 1] = arr[i]
count[index % 10] -= 1
i -= 1
for i in range(n):
arr[i] = output[i]
def radix_sort(arr):
max_num = max(arr)
exp = 1
while max_num // exp > 0:
counting_sort(arr, exp)
exp *= 10
