기수 정렬(Radix Sort) 알고리즘이란?

기수 정렬(Radix Sort)는 자릿수를 기준으로 데이터를 정렬하는 알고리즘입니다
특이한 것은, 배열의 값을 비교하는 방식의 정렬 알고리즘이 아닙니다

기본 원리

자릿수 0~9를 의미하는 버킷 배열을 만듭니다
따라서 추가적인 메모리가 사용됩니다

각 자릿수를 뽑아서 일치하는 자릿수 배열에 배치시킵니다
이러한 방식을 가장 자릿수가 큰 값만큼 반복합니다

이 과정에서 비교없이 단순히 자릿수의 위치만 배치하는 방식으로 정렬을 진행할 수 있습니다

시간복잡도

기수 정렬 알고리즘의 시간복잡도에 대해 알아보겠습니다

• n: 정렬할 항목의 수
• k: 항목 중 가장 큰 자릿수
• b: 진법 (보통 10진법)

따라서 시간복잡도는 O(k x (n + b) 입니다

만약 모든 숫자의 크기가 비슷하고 최대 자릿수 k가 log(n)의 크기라면
시간복잡도는 O(nlogn)과 비슷합니다

평균,최악, 최선

기수 정렬은 모든 경우에서 O(k x (n + b))의 시간복잡도를 가집니다
k의 값에 따라 성능이 좌우되며, k가 커진다면 퀵정렬같은 O(nlogn) 비교 정렬이 더 빠를 수도 있습니다

공간복잡도

기수 정렬은 추가 메모리가 필요합니다
각 자릿수 분류를 위한 버킷(배열)을 사용합니다
보통 0~9개까지의 10개 버킷이 만들어집니다

기수정렬의 공간복잡도는 O(n + b)입니다

이때 n은 입력 데이터의 수, b는 버킷의 개수입니다
사실상 O(n)의 추가 메모리가 필요합니다

입력크기가 커질 수록 필요한 메모리 사용량이 커지므로,
대규모 데이터셋이라면 기수 정렬을 사용하는 것에 대한 고민이나
메모리 최적화에 대해 고려해야합니다

장점

Radix Sort의 장점은 다음과 같습니다

비교 기반 정렬보다 빠를 수 있다

• n이 크고, 자릿수 k가 작을 때, 성능이 좋습니다
• 예를 들어, 수천만 개의 전화번호, 학생 ID 같은 경우는 Radix Sort가 퀵소트보다 빠릅니다

안정 정렬

• Radix Sort 역시 항목의 순서를 유지하는 안정 정렬입니다
• 따라서 항목의 순서를 유지해야하는 상황에서 장점이 될 수 있습니다

일관된 시간복잡도

• 퀵 정렬처럼 O(n²) 이 되지 않고, 최악의 경우에도 O(k × n) 을 유지합니다

단점

기수정렬의 단점은 다음과 같습니다

메모리 소모가 크다

• 입력 크기(n) 만큼 추가 메모리가 필요합니다
• 메모리가 적은 환경이라면 부담될 수 있습니다

데이터 타입에 제한이 있다

• 정수나 고정 길이 문자열에만 적용하기 쉽습니다
• 부동소수점(floating point) 같은 복잡한 자료형을 다루려면 추가 작업이 필요합니다

메모리와 버킷 관리비용 증가

• 진법에 따라 버킷 수가 커지면 메모리와 버킷 관리 비용이 증가합니다
• 예를 들어 16진수로 하면 버킷이 16개 필요합니다

자릿수 의존성

• 데이터의 최대 자릿수(k)가 크면 정렬 시간이 늘어납니다
• 예를 들어 32자리 숫자라면, 32번 스캔해야 하므로 비효율적입니다

결론

기수 정렬은 비교기반이 아닌 자릿수 기반의 정렬 알고리즘입니다
정수나 고정 길이 데이터가 많은 경우, 빠르고 효율적인 성능을 보이나
추가적인 메모리를 사용한다는 단점을 가지고 있습니다