기수 정렬 (Radix Sort)

기수 정렬(Radix Sort) 의 개념 요약

자릿수를 기준으로 차례대로 데이터를 정렬하는 정렬 알고리즘이다. 

여기서 '기수' 라는 것은 '자릿수' 를 의미한다.

 

 

구체적 개념

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘이다. 

비교 연산을 하지 않아서 정렬 속도가 빠르지만

데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

 

이 메모리는 기수 정렬에서 '버킷' 이라고 불리는데 숫자에 알맞게 새로운 공간에 값을 임시적으로 저장해주는 것이라고 생각하면 된다. 밑에서 더 자세히 설명하겠다. 

​

가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit)라고 한다.

가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Digit)라고 한다.

 

 

예제

→ 배열에 152, 73, 69, 41, 28, 1247, 2, 33, 674, 388이 저장되어 있다고 가정하고 오름차순으로 정렬해 보자. 

(LSD방식 이용)

 

 

1. 가장 큰 숫자는 1247이고, 자릿수는 4이다. 

 

 

2. 가장 작은 자릿수부터 가장 큰 자릿수까지를 기준으로 하여 정렬한다. 

   

    여기서 버킷은 총 10개가 존재한다. 

    그 이유는 0 ~ 9에 대한 버킷이다. 즉, 1의 자리가 0인 원소는 0번 버킷에, 1의 자리가 1인 원소는 1번 버킷에 등 이런

    식으로 담기게 된다. 

 

• 1의 자리수를 기준으로 정렬한다.

 

       위의 파랑색으로 적은 것은 버킷 칸이고, 그 밑에 적힌 값들은 버킷에 해당되는 값들을 적은 것이다. 

       즉, 예를 들어 0번 버킷이 의미하는 것은 1의 자리 숫자가 0인 원소들은 여기로 오세요를 의미한다.

 

       이 상태에서 다시 값들을 순차적으로 뺀다면 다음과 같이 배열이 1의 자리를 기준으로 정렬됨을 확인할 수 있다.

 

 

• 정렬된 배열에서 10의 자리수를 기준으로 또 버킷에 담아주면 된다. 

      이때, 1의 자리 숫자인 '2'같은 경우에는 '02'로 보고 10의 자리 숫자가 0인 곳에 들어가게 된다. 

      또 이 버킷을 순차적으로 꺼내어보면 배열이 10의 자리를 기준으로 다음과 같이 오름차순 정렬될 것이다. 

 

 

• 정렬된 배열에서 100의 자리수를 기준으로 또 버킷에 담는다.  

    순차적으로 마찬가지로 빼내보면 다음과 같다. 

 

• 이제 1000의 자리를 기준으로 버킷에 담는다. 

    순차적으로 빼내보면 정렬이 완성됨을 확인할 수 있다. 

    이렇게 최대 자릿수까지 계속해서 반복한다.

    이 예제에서 가장 큰 숫자 1247의 자릿수가 4이므로 정렬이 종료된다.

 

 

 

기수 정렬에서의 버킷

기수정렬은 '버킷'이라는 추가적인 공간할당이 필요하다.

가장 일반적으로 사용되는 것이 Queue이다.

 

왜냐하면 Queue는 FIFO 구조로써 먼저 들어간 값이 먼저 나오기 때문에 들어간 순서 그대로 빼내주기만 하면

그것이 위 예제에서 설명한 순차적으로 꺼내는 것과 동일한 역할을 하기 때문이다.

 

Queue에 적절한 Index에 원소를 push하고, 

Queue를 10인 크기의 배열로 만들어 기수 정렬의 버킷을 만들 수 있는 것이다. 

 

 

 

시간복잡도

시간복잡도는 최대자릿수 까지 N번 탐색하기때문에 O(N)이다. 말도 안되게 빠른 정렬 방법이라고 볼 수 있다.

 

위 예제처럼 만약 10개의 값이 있고 최대자릿수가 4이라고 가정했을 때

 

1의 자릿수를 찾는 과정에서 = 10번 탐색

10의 자릿수를 찾는 과정에서 = 10번 탐색

100의 자릿수를 찾는 과정에서 = 10번 탐색

1000의 자릿수를 찾는 과정에서 = 10번 탐색

 

즉 4 x 10 번 탐색을 하게된다. 이를 식으로 써보면 K * N번 탐색을 하는 것이고

이를 빅오 표기법으로 나타내면 O(N)이 된다.

 

 

하지만 !

이 정렬법이 제일 좋다고 생각할 수도 있지만 절대 그렇지 않다.

왜냐하면, '버킷'이라는 작지 않은 용량의 추가적인 메모리 공간이 필요하기 때문이다.

 

이것이 기수정렬의 최대의 단점이라고 볼 수 있다. 시간이 굉장히 빠르지만 추가적인 메모리 공간이 필요하기도 하고

버킷에 담고 빼는 과정도 양이 많아진다면 결코 무시할 수 없을정도로 시간을 잡아먹기 때문이다.