기수 정렬 ( Radix sort )

radix sort라고 네이ㅂ나 구ㄱ에 검색하면 한글 검색 자료로 기수 정렬이라고 나온다. 매-우 익숙치 않은 표현이다. 대학교에 와서 처음 [라딕스 소트]로 배운 탓인지 기수 정렬은 도저히 입에 붙질 않는다. 학부 알고리즘개론 조교를 하다보니까 여러 가지를 되새김질하는 중이다. 숙제 문제를 제출하고 보니 구현상의 문제들이 바로 와닿지 않아서 파이썬으로 한 번 짜봤다. ㅋㅋㅋㅋㅋ

---

이번에 소개할 radix sort는 선형 시간 내에 정렬할 수 있다고 알려진 정렬 방법이다. 평소에 우리가 하는 정렬들의 특징을 살펴보면서 radix sort를 소개할 것이다.

카드 게임을 해본 사람이라면 insertion sort의 경험이 있을 것이다. (그게 뭔지 몰랐을 뿐...)

삽입 정렬 ( insertion sort ) 은 어떤 한 카드를 골라서 제대로된 위치에 다시 꽂아넣는 것을 (최대로) 카드 개수만큼 반복하면 종료되는 알고리즘이다. 보통 사람이 섞인 카드들을 손에 들고서 왼쪽부터 오른쪽으로 정렬할 때 사용한다. 똑똑한 사람은 삽입 횟수를 최소한으로 하면서 정렬하는 기준을 가지고 있을 수 있지만 뭐...그러려니...

삽입 정렬은 카드 개수가 많아지면 정렬 속도가 굉장히 느려진다. 대충 O( n^2 ) 정도의 복잡도를 갖는다. 그리고 추가 저장 공간은 한 칸만 필요하고, 상대적인 위치가 유지되는 in-place 성질을 지니고 있다. 무슨 말이냐면, 2, 2', 이 값들이 모두 2라고 할 때, 1 2' 2 0 2'' 3 을 정렬하면 0 1 2' 2 2'' 3과 같이 2' 2 2''은 상대적인 위치들이 유지된다는 뜻이다.

radix sort도 in-place 성질을 지닌다. 내 생각에 radix sort를 이해하는 데 있어서 가장 중요한 특징이 in-place 성질이다. 왜 radix sort가 성공하는지 생각해볼 때 이 특징을 알면 금새 이해할 수 있다. 

그림에서 보면 십진법으로 나타낸 숫자들이 총 7개가 있다. 일의 자리수부터 백의 자리수로 기준을 옮겨가면서 각 자리수가 순서대로 정리되게끔 정렬하면 된다. 십진법은 0부터 9까지 총 10가지 숫자를 표기한다. 10개의 새로운 배열을 준비해서 주목하고 있는 자리수가 서로 같은 원소들끼리 동일한 배열에 모은다. 이후 0부터 9 순서로 배열을 합하는 방식으로 한 단계씩 진행시키면 된다. 낮은 자리수 기준으로 이미 정렬되어 있고, 상대적인 위치를 유지한 채로 높은 자리수 기준으로 정렬하는 것을 반복하다보면 전체 숫자들이 자연스럽게 정렬된다. 이는 자리수가 서로 달라도 시행할 수 있다. 만약 위 그림의 예시에서 2라는 숫자가 어딘가에 추가된다면 십의 자리 숫자와 백의 자리 숫자는 0으로 취급해버리면 된다.

radix sort를 처음 접할 때 특징적인 것은 배열 안에 있는 숫자들끼리 비교하질 않는다는 것이다. 삽입 정렬, 선택 정렬, 거품 정렬, 퀵 정렬 등등은 각각의 원소들끼리 비교를 통해 상대적인 순서를 정하게 된다. 근데 이 radix sort는 그렇지 않다. 그저 각 자리 숫자들 순서대로 정렬하는 행위를 자리수만큼 반복하면 된다. 

비교를 통해 정렬하지 않기에 비교에 기반을 둔 다른 정렬들의 최소 시간 복잡도인 O( n log(n) )과 달리 O(n) 시간으로 정렬한다는 특징이 있다. 따라서 선형 시간 알고리즘이라고 부르게 된다.

근데 나는 생각이 좀 다르다. 느낌상(?) 선형 알고리즘 앞에 붙는 상수값이 매우 클 것이란 생각이 들었고, 실제로 구현해보니까 꽤 많은 cost가 추가로 발생했었다. 위 예시처럼 3자리 수라고 이미 정해두지 않았다면 최대 자리수를 가진 숫자를 찾는 것만 해도 cost다. 자리수 digit별로 따로 임시 저장소를 만들어서 합쳐야되니까 그때 발생하는 출입 과정도 cost다. 심지어 음수가 끼어있으면 음수/양수를 나눠서 계산해야하므로 또 cost가 든다.

이런 과정을 생각해보면 결국 O(n)이라기보단 O(d*n)과 같은 시간복잡도를 구할 수 있다. 여기서 d는 배열 안 숫자들의 자리수 최댓값이다.

그리고 컴퓨터는 float number 표현이 매끄럽지 못하기 때문에 자리수 연산을 제대로 수행하지 못한다. 따라서 배열의 아이템들을 정수로 표현할 수 있을 때만 radix sort를 사용할 수 있다. 예를 들어, ascii 문자로 나타낼 수 있는 특수문자들이나 기본 정수들은 가능할 것이다. 

마지막으로 언급하고 싶은 것은 음수 표현에 대한 radix sort과정이다. 위에서 잠깐 언급했듯이 음수는 음수들끼리 따로 처리한 뒤에 양수 집합과 합쳐야한다. 음수들끼리 처리할때도 각 자리에 대한 임시 저장소에 숫자를 넣었다가 순서대로 이어붙이는 방식으로 숫자들의 순서를 맞춰 나간다. 이때 재밌는 것은 나머지 연산을 할 경우 결과는 양수라는 점에 있다. 사실 파이썬의 경우 index가 음수인 배열 접근을 허용하기 때문에 큰 문제가 발생하지 않았겠지만 다른 언어를 쓰더라도 나머지 연산이 양수이기 때문에 각 자리수임시 저장소 배열에 접근하는 것에 큰 문제가 발생하지 않았을 것이다. 예를 들어서 자리수가 3인 음수는 (-3)%10 == 7 이기 때문에 7번 임시 저장소에 들어가는 식이다. -3보다 -2, -1이 더 크기 때문에 각각 8번, 9번 임시 저장소에 들어가게 되고 실제로 양수에서 시행했듯이 7,8,9번 임시 저장소를 순서대로 합치면 된다. 알고리즘을 적용시키는 배열이 음수 집합이냐, 양수 집햡이냐는 것에 따라 따로 구현할 필요없이 동일한 연산으로 동일한 결과를 얻어낼 수 있다. 

합치는 과정은 쉽다. 음수 배열과 양수 배열을 그대로 이어붙이면 된다. 구현상에서 이와 같은 [이어붙이기]가 많이 나오기 때문에 linked list와 같은 데이터 구조를 쓰는 것이 좋을 것이다. 나는 우선 구현의 편의성을 위해 list로 구현했다. 

---

github에 구현한 코드가 올라가있다. ( Link )