라딕스 정렬: 알고리즘도 아름다울 수 있다는 사실, 7배 빠른 이유

프로그래밍 면접장, 백만 개의 32비트 정수를 빠르게 정렬하라는 질문을 받는 순간을 상상해봅시다. 흔히 퀵소트나 머지소트 같은 근접 선형 알고리즘을 떠올리지만, 실은 더 빠른 방법이 존재합니다. 바로 ‘라딕스 정렬’이죠. 이 글에서는 라딕스 정렬의 아이디어와 원리, 실제 적용 사례, 그리고 숨은 장점까지 쉽고 재미있게 풀어보겠습니다.

버블소트? 퀵소트? 백만 숫자엔 라딕스가 답!

소규모 데이터엔 버블소트, 선택소트, 삽입소트 같은 단순한 알고리즘으로도 충분합니다. 하지만 백만 개의 숫자를 다룰 땐 상황이 달라집니다. 이들은 시간 복잡도가 O(n²)라 엄청난 시간이 걸리죠. 그래서 퀵소트, 머지소트처럼 O(n log n)에 근접한 알고리즘이 주로 사용됩니다. 하지만, 라딕스 정렬을 활용하면 7배 가까이 빠른 속도를 낼 수 있다는 사실, 알고 계셨나요?

버킷 소트의 원리와 한계: 빠를 수도 있지만…

버킷 소트는 정수의 범위가 아주 작을 때 빛을 발합니다. 예를 들어 0부터 9까지 숫자 백만 개를 정렬한다면, 10개의 버킷을 만들고 숫자마다 해당 버킷에 넣는 방식으로 금세 답을 얻을 수 있습니다. 시간복잡도는 O(n + d)로 아주 효율적이죠. 하지만 32비트 정수(즉, 범위가 2³²)에 적용하면, 수십억 개의 버킷이 필요해 메모리와 실행시간에서 현실적으로 불가능합니다. 16비트까지는 빠르지만 32비트 이상에선 그야말로 백기입니다.

라딕스 정렬의 아이디어: 자릿수 하나씩, 두 번만으로 완성

여기서 라딕스 정렬이 등장합니다. 라딕스 정렬은 숫자를 여러 자릿수(‘기수’)로 나누어 각각 버킷 소트를 반복하며 정렬합니다. 예를 들어 두 자리 숫자라면, ‘일의 자리’로 한 번, ‘십의 자리’로 또 한 번 버킷 소트를 실행합니다. 처음엔 덜 중요한 자릿수부터, 점차 중요한 자릿수를 순서대로 살피죠. 이 과정이 중요한 이유? 바로 안정적인 정렬(stable sort)이기 때문입니다. 이전 버킷 정렬에서 결정된 순서가 다음 버킷 정렬에서 보존돼, 마지막엔 완벽하게 정렬된 결과가 나오게 됩니다.

자릿수와 버킷의 개수, 그리고 실제 성능 비교

실제로 32비트 숫자를 16비트씩 두 번 버킷 소트로 처리할 수 있습니다. 즉, 65,536개의 버킷만으로 되니 메모리 문제가 사라지고, 두 번의 반복만으로 백만 개의 데이터를 정렬할 수 있습니다. 성능 테스트 결과, 라딕스 정렬은 퀵소트보다 약 7배 빠른 속도를 보입니다. 단, 작은 데이터에는 라딕스가 오히려 느릴 수 있습니다(버킷을 순회하는 고정 비용 때문). 이땐 기수(자릿수)를 더 줄여 리소스를 아끼는 최적화도 가능합니다.

옛날엔 기계가 정렬했다: 60년 된 펀치카드 머신의 이야기

라딕스 정렬은 컴퓨터 이전부터 존재했습니다. 실제로 1950년대 독일에서 제작된 펀치카드 분류기가 라딕스 정렬을 기반으로 동작했죠. 펀치카드에는 필요한 정보(예: 자동차 부품, 병원 환자 데이터)가 구멍으로 저장되어 있었는데, 이 기계가 자릿수대로 한 번, 또 한 번 정렬하는 과정으로 데이터를 완벽하게 분류했습니다. 단순하고 직관적이지만, 기술의 아름다움이 느껴지는 순간입니다.

라딕스는 정수와 부동소수점에도 적용 가능할까?

보통 라딕스 정렬은 ‘양의 정수’에 한정된다고 알려져 있습니다. 하지만 진짜 재미있는 점은, 손쉬운 비트 해석만으로 부동소수점(float) 데이터에도 그대로 적용할 수 있다는 겁니다. IEEE 부동소수 표현 방식이 ‘최상위 비트에 부호, 그 다음엔 지수랑 가수’를 넣어서 만든 이유가, 비트 비교만으로도 값을 순서대로 나열할 수 있게 하기 때문이죠. 그래서 배열만 reinterpret해서 라딕스 정렬을 돌리면, float도 초고속으로 정렬됩니다. 네, 프로그래머라면 이 해킹을 사랑하거나 극혐하거나 둘 중 하나입니다!

왜 라딕스 정렬이 기본이 아니라 퀵소트가 기본일까?

라딕스 정렬은 규격화된 양의 정수나 특정 타입에서 탁월한 속도를 보이지만, 범용성은 비교 기반(퀵소트, 머지소트)에 비해 떨어집니다. 예를 들어 문자열, 객체, 혹은 음수 데이터에는 바로 적용이 어렵죠. 다양한 타입을 다루는 표준 라이브러리는 당연히 범용성, 안전성, 메모리 관리 등 여러 이슈를 함께 고민해야 하니까 어느정도 느려질 수밖에 없습니다. 반면 특정 목적·정의가 확실한 문제라면 라딕스처럼 ‘가장 단순한 해결책’이 때때로 최고의 성능을 선사하곤 합니다.

마무리하며, 라딕스 정렬의 장점은 극한의 속도와 우아한 원리에서 비롯됩니다. 대규모 정수 데이터를 다룬다면, 또는 성능이 정말 중요한 순간엔 라딕스를 꼭 떠올려보세요. 때로는 표준을 따르는 것보다 한 수 앞선 선택이 더 큰 효율을 만들어냅니다. 프로그래밍 문제의 핵심을 정확히 파악할 때, ‘OTT 알고리즘’(우리에게 딱 맞는 것!)을 선택하는 것도 최고의 실력입니다. 당신의 코드도, 커리어도 보다 빠르고 우아하게 나아가길 응원합니다!