[자료구조] 기수 정렬(Radix Sort)

 

기수 정렬이라고 번역되는 Radix Sort, 자릿수 정렬이라고 생각하면 이해가 더 쉬울 것이다. 기수 정렬은 말 그대로 자릿수와 정수를 이용해서 정렬을 하는데, 정수로 이루어진 배열을 정렬할 때 유독 사용하기 좋다. 한 번 살펴보자.

 

 

0부터 9를 담을 수 있는 큐 10개를 만든다. 여기서 큐를 만든 것은, 먼저 들어간 원소를 쉽게 제거할 수 있는 FIFO 자료구조를 사용한 것이다. 큐 대신에 리스트나 덱을 이용해도 구현은 할 수 있겠지만, 큐를 예시로 들어보겠다.

 

입력으로 예시 삼을 리스트가 [170, 45, 75, 90, 2, 802, 2, 66] 라고 가정하자. 여기서 각 정수들의 1의 자릿수만 살펴보면 다음과 같다.

 

[0, 5, 5, 0, 2, 2, 2, 6]

 

1의 자릿수의 숫자에 맞게 해당 숫자를 큐에 집어넣는다. 아래 그림 처럼.

 

숫자를 큐에 넣었으면 0부터 9까지 순서대로 숫자를 꺼내서 리스트를 만든다.

 

[{170, 90}, {2, 802, 2}, {45, 75}, {66}]

 

아래와 같이 될 것이다. {}는 신경쓰지 않아도 된다.

 

이제 10의 자릿수를 살펴본다. 10의 자릿수 숫자들을 살펴보면 [7, 9, 0, 0, 0, 4, 7, 6]이 됨을 알 수 있다. 여기서 중요한건 2와 같은 한 자릿수의 10의 자릿수는 0으로 취급한다는 것이다. 그래서 2는 '02'로 취급하여 0번째 큐에 넣는다. 숫자를 큐에 넣었으면 0부터 9까지 순서대로 숫자를 꺼내서 리스트를 만든다.

 

[{02, 802, 02}, {45}, {66}, {170, 75}, {90}]

 

이제 100의 자릿수를 살펴보고, 똑같이 큐에 넣고 꺼내는 과정을 반복한다. 이 과정을 리스트의 최대 자릿수(위 예시에는 802의가 백 단위 숫자니까 100의 자릿수)까지 반복한다. 그러면 아래와 같이 정렬된 결과가 나오는 것을 볼 수 있다.

 

[{002, 002, 045, 066, 075, 090}, {170}, {802}]

-> [2,2,45,66,75,90,170,802]

 

---

 

시간 복잡도

O(d * n)의 시간 복잡도를 가진다. 여기서 d는 원소 중에서 정수의 최대 자릿수, n은 정렬할 정수의 갯수이다. d를 상수로 추리한다면, 실질적으로 시간 복잡도는 O(n)을 가진다. (왜 O(d * n)을 가지는지 이해가 안된다면 위 정렬 과정을 다시 한 번 살펴보라. d회만큼 n번 정수를 정렬하는 과정을 반복하고 있다!) 최악, 최선, 평균의 경우 모두 O(n)의 시간복잡도를 가진다.

 

공간 복잡도

0부터 9까지의 큐를 만들어야하고, 9,19,29,39,... 처럼 끝의 자릿수가 같을 최악의 경우를 생각해보면 큐 하나의 길이가 최대 n까지 길어질 수 있다는 판단을 할 수 있다. 따라서 공간 복잡도는 O(n+w)이며, 여기서 w는 큐의 갯수다. 여기서도 w를 상수로 추리한다면 실질적으로 O(n)의 공간 복잡도를 가진다고 볼 수 있다.

 

Stable?

동일한 키를 가진 원소들이 자릿수 별로 정렬이 될 때, 큐(queue)에 의해 입력된 순서대로 정렬이 되므로 stable하다.

 

 

기수 정렬은 여러개의 큐를 만들어야 한다는 메모리 부담이 생기기 때문에, 메모리를 아껴야 하는 환경에서는 quick sort를 대신 사용하는 것으로 고려를 해볼 수 있다. 대신에 GPU 연산, 게임에서는 Radix sort를 사용하기도 한다. 원리를 따져보면 정수 정렬은 쉽게할 수 있지만 실수, 문자열 정렬은 쉽지 않다.