저번 시간에 count sort를 한 적이 있었습니다. 어떤 것이였나요? 수의 최대값과 최소값의 차이가 작을 때 count 배열을 두어, 처리할 수 있었던 것이지요. 만약에 이 차이가 20억이면 어떨까요? 당연하게도, 어떤 수가 몇 개나 있는지 저장할 수 없을 것입니다.
radix sort (기수 정렬)을 사용하면 이 점을 해결할 수 있습니다. 이 글에서는 이에 대해 알아보도록 하겠습니다.
- counting sort
- radix sort [현재글]
하위 자리부터 정렬하기
20억이라는 큰 수는, 65536의 제곱보다는 작습니다. 65536은, 우리가 count 배열에 담아두기에 적합한 size입니다. 만약, -10억에서 10억까지의 범위를 가지는 수들로 이루어진 배열을 정렬해야 한다면, 어떻게 하면 될까요?
배열에 있는 모든 수에 10억을 더하고 시작합니다. 그러면, 65536a + b 꼴로 표현이 가능합니다. 단, a와 b는 0 이상 65536 미만의 정수입니다. 여기서 시작합니다. 이렇게 표현될 때, a는 65536으로 나누었을 때의 몫, b는 나머지라고 생각할 수 있습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd4-1.png)
먼저, 나머지가 0인 것, 1인 것, 2인 것 순서대로 정렬합니다. 즉, 나머지가 작은 순으로 먼저 정렬합니다. 그 다음에는 어떻게 하면 될까요? 첫 번째 원소부터 차례대로 훑으면서, 몫이 작은 순으로 정렬하면 됩니다.
- 나머지 오름차순으로 정렬합니다.
- 몫 오름차순으로 정렬합니다.
만약 나머지 값인 b에 대해서 정렬이 되었다고 해 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd5-2.png)
그러면 a가 같을 때, b가 더 큰 것이 먼저 나올까요? 그러지 않습니다. 왜? b가 더 큰 것은 뒤에 나오는 것이 자명하기 때문입니다. 이미 b에 대해 오름차순으로 정렬했기 때문입니다. 한 개의 예제를 가지고 시뮬레이션을 해 보도록 하겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd6.png)
배열이 요렇게 있었습니다. 먼저, 나머지 오름차순으로 정렬해 봅시다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd7.png)
그러면, 65536, 0이 먼저 나오고, 다음에 1, 131073, 그 다음에 2가 나옵니다. 2순위 기준으로 먼저 sort 했다는 것이 중요합니다. 다음에, 이 상태에서 몫을 기준으로 정렬하겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd8.png)
그러면, 0, 1, 2가 먼저 나오고, 다음 몫이 1인 65536, 그 다음에 몫이 2인 131073 이렇게 정렬이 됩니다. 중요한 것은 그림에 있는 화살표가 교차되지 않았다는 것입니다. 만약에, 화살표가 교차되었다면, stable 하지 않습니다. rank가 같은 데 자리가 바뀌었기 때문입니다.
즉, 나머지를 기준으로 먼저 stable sort를 하고, 몫을 기준으로 stable sort를 하면 문제 없이 돌아갈 것이 자명합니다. 여기까지 코드를 보겠습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd1.png)
먼저, -10억 ~ 10억 사이의 수가 들어온다고 하였을 때 처리하는 부분입니다. 14번째 줄과, 18번째 줄은 왜 있는 것인지는 아실 것이라 생각합니다. 8번째 줄의 3번째 인자는 함수 포인터인데요. 몫을 리턴하는 경우와, 나머지를 리턴하는 경우가 있기 때문에, function pointer로 rank를 불러오는 부분을 처리하였습니다.
이제, radix sort 함수와 get_mok, get_namo 함수 내부로 들어가 봅시다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd3.png)
먼저 get_mok은, 65536으로 나누었을 때 몫을 구합니다. get_namo는 나머지를 구해요. bit 연산으로 보다 빠르게 처리했음을 알 수 있습니다. 다음, radix_sort 함수의 내부를 보면, work를 2번 호출합니다. 그런데, 3번째 인자가 달라요. 한 번은 get_namo를, 다른 한 번은 get_mok을 호출하는데요. 이는, rank를 구할 때 먼저 나머지를 기준으로 정렬하고, 그 다음에 몫을 기준으로 정렬하기 때문입니다.
rank 별로 원소 모으기
work 함수는 rank 별로 원소를 모으는 역할을 합니다. 사실, 이게 제일 중요합니다. 이것을 어떻게 해야 할까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd9.png)
먼저 rank가 x인 것의 개수를 셉니다. 예를 들어 rank(x)가 x의 나머지라고 해 보겠습니다. 그러면,
- 나머지가 0인 것과 1인 것의 개수는 2입니다.
- 나머지가 2인 것의 개수는 1입니다.
따라서 co 배열은 위 그림과 같이 나오게 됩니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd10.png)
이를 토대로, rank가 x인 수가 최초로 나오는 지점을 pos[x]로 정의합니다. 이 경우, rank(x)를 x로 나누었을 때 나머지로 정의하였습니다. rank가 0인 것이 먼저 나오고, 1인 것이 다음에, 2인 것이 그 다음에 나온다면
- rank[0]의 최초 pos 값은 0입니다.
- rank[1]의 최초 pos 값은 rank가 0인 것의 개수입니다.
- rank[2]의 최초 pos 값은 rank가 0, 1인 것의 개수입니다.
이는 누적합 배열로 처리 가능합니다. 이렇게 구축해 놓은 것이 어떻게 쓰일까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd11.png)
노란색은 rank가 0인 것, 파란색은 1인 것, 빨간 색은 2인 것입니다. 먼저, 65536을 읽습니다. rank가 0이지요? 따라서, 진한 노란색이 가리키고 있는 0번째 위치에 넣습니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd12.png)
temp에, 65536이 들어간 상태입니다. 그 다음에 어떻게 되었나요? 노란색이 가리키는 것이 하나 증가했습니다. 이제 1을 읽어볼까요?
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd13.png)
1을 65536으로 나누었을 때 나머지는 1이므로, 1의 rank는 1입니다. 따라서, 2번째 위치에 1이 들어가고, 군청색은 그 다음 원소를 가리키게 됩니다. 이런 알고리즘으로 모든 원소에 대해서 다 채워나가면, 아래와 같이 채워집니다.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd14.png)
이 과정 얼마나 걸릴까요? 배열의 크기가 n이고, radix 진법으로 처리한다면 O(n + radix)만큼 걸립니다. 이제 코드를 볼게요.
![](https://codingdog.pe.kr/wp-content/uploads/2023/09/rd2.png)
work 함수는 크게 4부분으로 이루어져 있습니다. 여기서, func는 rank를 구하는 함수입니다.
- rank가 x인 것을 count 한다.
- 누적 배열 pos를 구축한다. 이를 토대로 rank가 x인 수가 들어갈 위치를 알 수 있다.
- 우리는 pos를 알기 때문에
- rank가 t인 수의 위치가 pos라면 pos 번째에 집어넣는다.
- 그리고 pos[t]의 값을 증가시킨다.
- 원본 배열에 처리 결과를 복사한다.
이 글에서 1 ~ 3번까지 개략적인 알고리즘을 설명하였습니다. radix sort는 work를 호출하는 횟수에 지배됩니다. work의 시간 복잡도는 O(n + radix)이고, work의 호출 횟수는 최대값과 최소값의 차이에 로그 radix를 씌운 것입니다. radix가 크고, 최대값과 최소값의 차이가 20억이나 900경이면, 그리 크지 않으니, O(n + radix)라고 보셔도 됩니다.