Algorithm #1. Sort algorithm. - 1.6 Radix Sort algorithm.

이번엔 기수 정렬, Radix Sort 대해 알아보죠.

 Radix Sort 는 기본적으로 비트열을 정렬 대상으로 삼는 알고리즘입니다.

그래서 숫자 배열에 대해서는 매우 효율적인 알고리즘 중 하나입니다만, 문자 배열에 대해서는 탐색해야 할 비트열이 많아지므로
그다지 효율적인 선택이 아닙니다. 이 경우엔 다른 Sort 알고리즘을 선택하는걸 추천하죠.

우선 Radix Sort 는 두 가지로 나뉘어 집니다.

1. Radix Exchange Sort(기수 교환정렬)

2. Straight Radix Sort(직접 기수정렬)

흠... 그 중 Radix Exchange Sort 는 가장 직관적인 방법이라 할 수 있겠군요. 일상생활에서 우리가 가장 즐겨쓰는 방법입니다.

보통 인간은 10진법 체계를 사용합니다.

따라서, 각 자리수 별로 가장 큰 수는 9 이며, 가장 작은 수는 0 입니다.

그리고 우리가 수를 비교하는 방법은 다음과 같죠.

1. 몇 자리 수인지 비교한다.
   
2. 자리 수가 같다면 -> 그 자리 수의 크기를 비교한다. 이 경우 9 가 가장 크며, 0 이 가장 작다.

3. 자리 수의 크기가 같다면 -> 다음 자리 수로 넘어간다.

4. 큰 수가 결정될 때 까지 2 -> 3 번 알고리즘을 반복 수행.

5. 1번째 자리 까지 자리 수가 같다면 -> 같은 수이다.

-_-a 가장 익숙한 방법이죠?

그리고, 모두 아시다시피 컴퓨터는 몇 진법 수를 쥐어주든 2진수로 변환해서 값을 사용합니다.
2진 비트열의 제일 왼쪽 비트는 가장 큰 자리 수를 의미하죠. 그러므로 우리가 일상에서 이용하는 알고리즘을 적용할 수 있습니다.

따라서, Radix Exchange Sort의 구현은 두 가지 방법으로 생각해 볼 수 있겠죠.

1. 모든 입력값을 비트화 해서 왼쪽부터 탐색해 들어간다.

2. 굳이 비트화 할 필요 없이 자리수만 왼쪽부터 비교해 들어간다.
   - 정수 배열에 한해서 사용 가능한 방법. -

사실 컴퓨터 내부 구조를 생각하면 그게 그겁니다만... 2번째 방법으로 코드를 작성하면 훨씬 더 직관적으로 작성가능하겠죠.

하지만 기본적으로는 비트화하는 방법을 이용합니다.



두 번째로, Straight Radix Sort 입니다.

우선 Radix Exchange Sort 와의 차이점부터 설명해야 할까요.

Radix Exchange Sort 는 왼쪽부터 탐색해 들어간다고 말씀드렸을 겁니다.

하지만 Straight Radix Sort 는 오른쪽, 즉 비트열의 제일 끝부터 탐색합니다.
- 제일 작은 자리죠. -

"그렇다면 어떻게 정렬이 가능하지? " 라고 생각하실지도 모르겠군요.

하지만 이 경우에 한해서 사용가능한 아주 재미있는 알고리즘이 있습니다.

바로 Distribution Counting. 분포수 세기라고 번역되는 알고리즘이죠.

Distribution counting 을 위해선 먼저 입력받은 배열의 레코드를 쭉 검색해서 나타나는 값들의 빈도를 구해야 합니다.
- 배열을 사용하는 편이 간단하죠. -

그 이후 각 값들의 빈도에 대한 누적 합계를 구하고, 이를 기준으로 삼아 레코드를 정렬합니다.
- 이 경우, 누적 합계를 계산하기 위한 배열 - 빈도를 계산한 배열 - 은 모두 오름차순으로 정렬되어 있어야 합니다.
예를 들자면, 1 에 대한 빈도 , 2 에 대한 빈도, 3 에 대한 빈도, 4 에 대한 빈도, ........ n 에 대한 빈도.
이런 식이겠죠. -

단, 이 알고리즘의 경우는 출현하는 값의 분포가 클 수록 너무나 비효율적이 됩니다.
따라서 일반화시켜 사용하기엔 힘든 알고리즘이죠.

... 단, 지금 우리가 논의하는 주제에는 아주 안성맞춤이라 할 수 있습니다.

비트열은 Binary. 즉 1 과 0 의 조합입니다. 값의 분포수는 2 밖에 되지 않죠.

따라서, 정렬할 레코드들을 세로로 쭉 나열해 놓고 오른쪽부터 비트열을 Distribution counting 을 사용해서 정렬해 가는 것이
Straight Radix Sort 의 기본적인 방법론입니다.

하지만, 이렇게 복잡하게 비트화 시켜서, 또 Distribution counting 이라는 알고리즘까지 복합시켜서 정렬할 바에야 차라리
다른 정렬 알고리즘을 선택하는 게 최선이겠죠.
- 역시 비트열을 이용하는지라, 정수 배열에만 효율적이라는 한계도 작용하구요. 그나마도 레코드 수가 크면 적용이 힘들죠. -

그러나, Straight Radix Sort 를 사용하는 이유가 있습니다.
바로, Distribution counting 을 응용하면 '복합' 비트열에 대해서 정렬 연산이 가능하다는 거죠.

즉, 오른쪽 부터 비트열을 검색하되, 2 개, 4 개, 8 개, 16 개, ......

복합 비트열에 대한 동시 정렬이 가능합니다. 곧, 20개의 레코드를 동시 4개 비트열 동시 검색을 이용한 Straight Radix Sort 라면
단 5회만에 정렬이 가능하다는 거죠.



그럼 이제까지의 Radix Sort 를 정리해 볼까요.

1. Radix Exchange Sort.

- 우리가 일상 생활에서 사용하는 알고리즘을 이용한다.
  즉, 가장 큰 자리의 비트열 부터 비교, 검색하는 알고리즘이다.

- 가장 왼쪽 비트 (or 자리수) 부터 정렬 시작한다.

- 기본적으로 비트화 해서 정렬하나, 정수 배열에 한해서는 자리별로 끊어서 구현하는 방법도 생각해 볼 수 있다.

2. Straight Radix Sort.

- 오른쪽 비트부터 정렬시도한다.

- 기본적으로 Distribution Counting 기법을 이용하여 정렬한다.
 
- 복합 비트열에 대해서 Distribution Counting 기법으로 동시 검색이 가능하므로, 빠른 정렬 결과를 얻을 수 있다.

3. 단점

- 레코드의 갯수가 매우 크다면 비효율적이다.  - 비트열 검색을 이용하므로. -

- 더욱이 만약 정렬할 레코드가 문자 배열이라면 매우 비효율적.

- Straight Radix Sort 의 경우, 복합 비트열 검색을 이용할 수 있긴 하나, 그 경우 희생되는 메모리의 양은 무시못할 수준이라는
   것이 알려져 있다. 주의할것.