라딕스 정렬: 60년 역사의 초고속 알고리즘 비밀
프로그래밍 면접에서 “100만 개의 32비트 숫자를 가장 빠르게 정렬하는 방법이 뭘까요?”라는 질문을 받으면 대부분은 퀵소트나 병합정렬을 떠올립니다. 하지만 실제로 몇 배 더 빠른 라딕스 정렬이란 알고리즘이 있죠. 이 정렬법은 이미 반세기 전에 등장했고, 오늘날 대용량 데이터를 다루는 데도 큰 힘을 발휘합니다. 한 번쯤 들어봤던 라딕스 정렬의 원리부터 실전 활용법, 그리고 독특한 역사까지 쉽고 재미있게 파헤쳐봅니다!
정렬 알고리즘의 속도 비교: 왜 라딕스가 특별할까?
일반적인 정렬 알고리즘은 입력 데이터의 크기가 커지면 느려집니다. 버블소트, 선택정렬, 삽입정렬처럼 비교 횟수가 많은 알고리즘은 백만 개의 숫자를 상대하기엔 너무 느리죠. 그래서 실무에선 O(N log N) 시간복잡도의 퀵소트나 병합정렬이 기본 선택이 됩니다.
하지만 라딕스 정렬은 데이터 형식만 맞는다면, 퀵소트보다 최대 7배 이상 빠른 성능을 보여줍니다. 입력이 아주 많을수록 그 차이는 더욱 벌어지죠. 대량 숫자 정렬 문제라면 라딕스 정렬이 성능의 게임체인저가 됩니다.
버킷 소트에서 라딕스 소트까지: 기본 원리 완전 해부
라딕스 정렬은 ‘버킷 소트’의 아이디어에서 출발합니다. 예를 들어 0~9 사이의 숫자 100만 개를 정렬해야 한다면, 10개의 ‘버킷’만 있으면 됩니다. 각 숫자를 해당 버킷에 쏙쏙 집어넣으면, 모든 버킷을 차례로 꺼내는 것만으로 정렬이 완성됩니다.
문제는 32비트 숫자처럼 값의 범위가 너무 넓어지면 버킷 소트의 효율이 떨어진다는 것. 2의 32승(약 43억 개) 버킷을 만들어야 하는데, 메모리부터 시간까지 감당이 안 되죠. 그래서 라딕스 정렬은 숫자를 여러 자리(비트 단위)로 쪼갠 뒤, 각 자리별로 차례차례 버킷 소트를 두 번 또는 여러 번 반복해 진행합니다. 대표적으로 32비트 숫자라면 16비트씩 두 번에 나누어 훨씬 적은 버킷을 이용해 정렬합니다. 임의의 자릿수마다 빠른 처리, 이게 라딕스의 핵심입니다.
라딕스 정렬의 스텝별 전략: 자리수 순서가 관건!
라딕스 정렬이 가능한 이유는 ‘안정(stable) 정렬’의 특징을 살리기 때문입니다. 가장 낮은 자리(예: 십의 자리)부터 버킷 소트를 반복하면, 더 높은 자리에서 소트할 때 각 그룹 내부의 순서가 이미 맞춰져 있어 전체적으로 완벽하게 정렬됩니다. 예를 들어 0~99 사이의 두 자리 숫자를 정렬한다고 할 때, 일단 일의 자리로 한 번 소트하고, 그 결과를 십의 자리로 다시 정렬하면 끝! 세 자리, 네 자리도 마찬가지로 각 자릿수별로 버킷 소트를 반복하면 매우 효율적으로 처리가 됩니다.
실제로 16비트 단위로 쪼개서 두 번만 소트하면, 100만 32비트 정수도 순식간에 정렬 가능합니다. 이 과정은 수많은 데이터 처리 현장에서 쓰이는 실전 노하우입니다.
라딕스 정렬의 태생: 60년 전의 기계식 펀치카드 정렬기
프로그래머들이 ‘라딕스 소트’를 쓰기 훨씬 전에, 1950년대에 이미 이 원리가 현실에서 쓰이고 있었답니다. 독일 프랑크푸르트의 기술 박물관에는 1960년대 펀치카드를 정렬하던 기계가 있습니다. 이 기계는 플러그나 CPU도 없이, 단순한 기계 장치로 라딕스 정렬을 실현했습니다. 두 자리 숫자를 가진 카드를 먼저 일의 자리로, 그 다음 십의 자리로 순차적으로 정렬해서 모든 카드의 순서를 완벽히 맞추는 모습을 직접 볼 수 있죠. IT 역사의 현장이기도 합니다.
한계와 확장: 퀵소트 대신 라딕스 소트를 언제 써야 할까?
라딕스 정렬은 장점만 있는 건 아닙니다. 반드시 ‘양의 정수’에만 사용 가능한 것, 입력이 몇십 개 수준으로 작으면 오히려 퀵소트보다 느릴 수 있다는 약점이 있습니다. 반면, 퀵소트나 병합정렬 같은 비교 기반 알고리즘은 정수뿐 아니라 실수, 문자열, 다양한 복합 객체에도 사용할 수 있죠. 이지점이 라딕스 소트의 한계이자, 사용하는 상황을 잘 판단해야 하는 이유입니다.
하지만 의외로 라딕스 소트는 ‘실수(float)’도 정렬할 수 있습니다. 컴퓨터의 메모리에서 비트만 보면, 어느 종류든 일련의 숫자로 해석할 수 있기 때문이죠. IEEE 표준에 맞게 저장된 실수라면 비트 배열 그 자체를 정수로 간주하여 라딕스 소트를 그대로 사용할 수 있습니다. 이건 알고리즘을 좋아하는 이들 사이에서 ‘논쟁거리’이기도 하죠!
실제 데이터 산업과 라딕스의 활용 사례
현재 라딕스 정렬 및 그 원리는 데이터 센터, 네트워크 라우터, 대규모 시스템에서 활발히 활용됩니다. 예를 들어 라우터에서 쓰이는 ‘라딕스 트리’ 자료구조는 빠른 IP