카운팅 정렬, 래딕스 정렬
16 Oct 2017 | counting sort radix sort
이번 글에서는 요소값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법인 카운팅 정렬(counting sort)과 래딕스 정렬(Radix sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고로 하였습니다. 그럼 시작하겠습니다.
comparison sort
두 개 요소값을 반복적으로 비교하여 정렬을 수행하는 알고리즘을 comparison sort라고 합니다. 이는 Decision tree 모델로도 불립니다. 정렬 대상 숫자가 세 개인 경우를 예로 들어보겠습니다. 아래 그림과 같습니다.
위 트리를 보면 3개 숫자를 정렬하는 데 가능한 경우의 수는 6개($3!$)입니다. 각 경우의 수가 트리의 말단노드(leaf)가 됩니다. 트리의 루트노드에서 말단노드까지의 엣지의 수를 해당 트리의 높이(height)라고 하고 일반적으로 $h$라고 표기합니다. 위 트리에서 $h$는 최종 정렬 결과를 산출하기까지의 비교 횟수를 가리키는데요. 위 그림에서는 3입니다. 이 $h$가 바로 comparison sort의 계산복잡성을 나타냅니다.
이진트리의 높이가 $h$일 때 최대 $2^h$개의 말단노드를 가집니다. 그런데 데이터 수가 $n$개일 때 정렬 가능한 모든 경우의 수($n!$)보다 말단노드의 수가 커야 최악의 경우에도 데이터의 모든 요소값들을 정렬할 수 있을 것입니다. 다시 말해 $2^h≥n!$이 성립해야 한다는 말입니다. 이 부등식 양변에 밑이 2인 로그를 취하면 $h≥\log{n!}$이 됩니다. 한편 팩토리얼 연산의 성질에 의해 $n!>\sqrt{2πn}(n/e)^n$이라고 합니다. $n$이 1 이상일 때 $\sqrt{2πn}$ 역시 1보다 큰 값을 가지므로 여태까지 말씀드린 내용을 모두 종합해 식으로 표현하면 다음과 같습니다.
\[h\ge \log { n! } >\log { \left\{ \sqrt { 2\pi n } { \left( \frac { n }{ e } \right) }^{ n } \right\} } >\log { { \left( \frac { n }{ e } \right) }^{ n } } \\ \Rightarrow h>\log { { \left( \frac { n }{ e } \right) }^{ n } } \\ \Rightarrow h>O\left( n\log { n } \right)\]
최종 도출된 부등식의 의미는 이렇습니다. 두 값을 반복적으로 비교해 정렬하는 기법인 comparison sort는 아무리 알고리즘을 잘 짜도 계산복잡성이 $O(n\log{n})$보다 크다는 말입니다. 바꿔 말해 comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. 예컨대 퀵 정렬(quick sort)의 계산복잡성이 $O(n^2)$이고, 힙 정렬(heap sort)이 $O(n\log{n})$이라는 점을 감안하면 이같은 내용이 들어맞음을 확인할 수 있습니다.
이 글에서 설명할 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산복잡성을 $O(n)$으로 낮추려는 알고리즘입니다.
counting sort
다음과 같은 입력어레이(input array) $A$에 대해 counting sort를 수행한다고 칩시다.
$A=[2,0,2,0,4,1,5,5,2,0,2,4,0,4,0,3]$
$A$의 모든 요소값의 빈도를 세어 카운팅어레이(counting array) $C$에 저장해 둡니다. $C$의 첫번째 요소 $c_1$이 3라는 5은 $A$ 가운데 0이 다섯 개 있다는 뜻입니다. 마찬가지로 $c_2$가 1이라는 말은 $A$에 1이 하나 있다는 말이 됩니다.
$C=[5,1,4,1,3,2]$
$C$의 각 요소값에 직전 요소값을 더해서 업데이트해 줍니다. 예컨대 $c_2$는 $c_1$(5)에 기존 $c_2$(1)를 더해서 만듭니다.
$C=[5,6,10,11,14,16]$
입력어레이와 같은 크기를 갖는 출력어레이(output) $B$를 만듭니다. 처음에는 비어 있습니다. 여기에서 바로 위의 $C$의 의미는 이렇습니다.
- $c_1=5$ : 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지한다.
- $c_2=6$ : 1은 $b_6$ 한 개 자리를 차지한다.
- $c_3=10$ : 2는 $b_7$에서 $b_{10}$까지 네 개 자리를 차지한다.
- $c_4=11$ : 3은 $b_{11}$ 한 개 자리를 차지한다.
- $c_5=14$ : 4는 $b_{12}$에서 $b_{14}$까지 두 개 자리를 차지한다.
- $c_6=16$ : 5는 $b_{15}$에서 $b_{16}$까지 두 개 자리를 차지한다.
$b_1$
$b_2$
$b_3$
$b_4$
$b_5$
$b_6$
$b_7$
$b_8$
$b_9$
$b_{10}$
$b_{11}$
$b_{12}$
$b_{13}$
$b_{14}$
$b_{15}$
$b_{16}$
이제 $A$ 요소값의 역순으로 $B$에 채워 넣습니다. 3은 $b_{11}$ 한 개 자리를 차지하므로 여기에 넣습니다. 아래와 같습니다. 이제 $b_{11}$의 자리가 채워졌으므로 $c_3$의 현재값(11)에서 1을 뺍니다.
$b_1$
$b_2$
$b_3$
$b_4$
$b_5$
$b_6$
$b_7$
$b_8$
$b_9$
$b_{10}$
$b_{11}$
$b_{12}$
$b_{13}$
$b_{14}$
$b_{15}$
$b_{16}$
3
다음은 0을 넣을 차례입니다. 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지하므로 $b_5$에 넣습니다. 아래와 같습니다. 이제 $b_{5}$의 자리가 채워졌으므로 $c_1$의 현재값(5)에서 1을 뺍니다.
$b_1$
$b_2$
$b_3$
$b_4$
$b_5$
$b_6$
$b_7$
$b_8$
0
$b_9$
$b_{10}$
$b_{11}$
$b_{12}$
$b_{13}$
$b_{14}$
$b_{15}$
$b_{16}$
3
이러한 방식으로 $A$의 모든 요소값을 $B$에 넣으면 다음과 같이 정렬이 종료됩니다.
$b_1$
$b_2$
$b_3$
$b_4$
$b_5$
$b_6$
$b_7$
$b_8$
0
0
0
0
0
1
2
2
$b_9$
$b_{10}$
$b_{11}$
$b_{12}$
$b_{13}$
$b_{14}$
$b_{15}$
$b_{16}$
2
2
3
4
4
4
5
5
두 값을 비교하는 과정 없이 정렬이 수행됐음을 확인할 수 있습니다.
파이썬 구현
카운팅 정렬을 파이썬으로 구현한 코드는 다음과 같습니다.
# A: input array
# k: maximum value of A
def counting_sort(A, k):
# B: output array
# init with -1
B = [-1] * len(A)
# C: counting array
# init with zeros
C = [0] * (k + 1)
# count occurences
for a in A:
C[a] += 1
# update C
for i in range(k):
C[i+1] += C[i]
# update B
for j in reversed(range(len(A))):
B[C[A[j]] - 1] = A[j]
C[A[j]] -= 1
return B
counting sort의 복잡성
데이터 개수가 $n$일 때 $A$의 빈도를 세는 계산복잡성은 $O(n)$입니다. 데이터 전체를 한번씩 훑어야 하기 때문입니다. 출력어레이 $B$를 만들 때도 $O(n)$입니다. $A$의 요소값들을 역순으로 모두 훑어야 하기 때문입니다.
한편 $k$는 $A$의 요소값 가운데 최댓값을 가리킵니다. 위 예시에서는 $k=5$였습니다. 카운팅어레이 $C$를 만들 때 $k+1$개의 요소값을 0으로 초기화하게 되므로 공간복잡성은 $O(k)$가 됩니다. 또한 $C$를 업데이트할 때 반복문이 $k$번 돌게 되므로 계산복잡성 또한 $O(k)$가 됩니다. 그런데 $A$가 만약 다음과 같다면 카운팅어레이 $C$의 크기가 10000+1이 되고, 반복문 또한 10000회를 돌게 되어 대단히 비효율적이게 됩니다.
$A=[0, 10000]$
요컨대 counting sort의 전체적인 계산복잡성은 $O(n+k)$가 되는데요. $k$가 충분히 작을 경우 $O(n)$이 되겠지만, $k$값이 커질 경우 $k$가 counting sort의 복잡성을 지배하게 됩니다.
Radix sort
입력데이터 $A$의 최대값인 $k$가 커지면 counting sort의 효율성은 크게 떨어집니다. 하지만 각각의 자릿수를 기준으로 정렬을 하게 되면 계산복잡성을 낮출 수 있습니다. 예컨대 10진법으로 표기된 숫자를 정렬한다면 $k$는 9가 됩니다. 이러한 정렬 방식을 Radix sort라고 합니다.
단 여기에서 주의할 것은 각 자릿수를 기준으로 정렬할 때 정렬 대상 숫자들의 위치가 뒤바뀌지 않는 stable sort 알고리즘을 적용해야 한다는 것입니다. 특정 자릿수를 놓고 정렬할 때 그 위치가 바뀌게 되면 해당 숫자가 아예 다른 숫자가 되어버리기 때문입니다. 예컨대 unstable sort를 적용하면 다음과 같은 엉뚱한 결과가 나올 수 있습니다.
14, 21 ==> 11, 24
radix sort를 연결리스트(linked list)로 구현할 수도 있습니다. 10진수 첫번째 자리를 기준으로 정렬한 뒤, 두번째 자리를 기준으로 정렬합니다. 정렬 순서를 유지하기 위해 연결리스트 삽입시 head에 넣지 않고 tail에 삽입하는 것이 특징입니다. 예컨대 아래 그림과 같이 12가 이미 있는 2번 버킷에, 22를 삽입하는 경우 12 앞이 아니라 뒤에 넣습니다. 다음 그림과 같습니다.
counting sort를 바탕으로 raddix sort를 구현한 파이썬 코드는 다음과 같습니다. counting sort도 대표적인 stable sort입니다.
# 현재 자릿수(d)와 진법(base)에 맞는 숫자 변환
# ex) 102, d = 1, base = 10, : 2
def get_digit(number, d, base):
return (number // base ** d) % base
# 자릿수 기준으로 counting sort
# A : input array
# position : 현재 자릿수, ex) 102, d = 1 : 2
# base : 10진수라면 base = 10
def counting_sort_with_digit(A, d, base):
# k : ex) 10진수의 최대값 = 9
k = base - 1
B = [-1] * len(A)
C = [0] * (k + 1)
# 현재 자릿수를 기준으로 빈도수 세기
for a in A:
C[get_digit(a, d, base)] += 1
# C 업데이트
for i in range(k):
C[i + 1] += C[i]
# 현재 자릿수를 기준으로 정렬
for j in reversed(range(len(A))):
B[C[get_digit(A[j], d, base)] - 1] = A[j]
C[get_digit(A[j], d, base)] -= 1
return B
다음은 Radix sort 코드입니다.
from math import log
def radix_sort(list, base=10):
# 입력된 리스트 가운데 최대값의 자릿수 확인
digit = int(log(max(list), base) + 1)
# 자릿수 별로 counting sort
for d in range(digit):
list = counting_sort_with_digit(list, d, base)
return list
Radix sort의 계산복잡성을 따져보겠습니다. counting sort이 $O(n+k)$이고 10진수를 예로 들 때 $k$는 9에 불과하므로, 특정 하나의 자릿수를 기준으로 counting sort하는 데 드는 비용은 $O(n)$이 될 것입니다. 그런데 전체 자릿수가 $d$라면 이를 $d$번 수행해야할 것입니다. 따라서 전체적인 복잡성은 $d×O(n)$이 됩니다. 1조($=10^{12}$)가 넘는 큰 숫자가 끼어 있어도 $d$는 12에 불과하기 때문에 선형시간에 가깝게 정렬을 수행할 수 있습니다.
이번 글에서는 요소값을 명시적으로 비교하지 않아도 정렬할 수 있는 기법인 카운팅 정렬(counting sort)과 래딕스 정렬(Radix sort)에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님 강의와 위키피디아, 그리고 이곳을 참고해 정리하였음을 먼저 밝힙니다. 파이썬 코드는 이곳을 참고로 하였습니다. 그럼 시작하겠습니다.
comparison sort
두 개 요소값을 반복적으로 비교하여 정렬을 수행하는 알고리즘을 comparison sort라고 합니다. 이는 Decision tree 모델로도 불립니다. 정렬 대상 숫자가 세 개인 경우를 예로 들어보겠습니다. 아래 그림과 같습니다.
위 트리를 보면 3개 숫자를 정렬하는 데 가능한 경우의 수는 6개($3!$)입니다. 각 경우의 수가 트리의 말단노드(leaf)가 됩니다. 트리의 루트노드에서 말단노드까지의 엣지의 수를 해당 트리의 높이(height)라고 하고 일반적으로 $h$라고 표기합니다. 위 트리에서 $h$는 최종 정렬 결과를 산출하기까지의 비교 횟수를 가리키는데요. 위 그림에서는 3입니다. 이 $h$가 바로 comparison sort의 계산복잡성을 나타냅니다.
이진트리의 높이가 $h$일 때 최대 $2^h$개의 말단노드를 가집니다. 그런데 데이터 수가 $n$개일 때 정렬 가능한 모든 경우의 수($n!$)보다 말단노드의 수가 커야 최악의 경우에도 데이터의 모든 요소값들을 정렬할 수 있을 것입니다. 다시 말해 $2^h≥n!$이 성립해야 한다는 말입니다. 이 부등식 양변에 밑이 2인 로그를 취하면 $h≥\log{n!}$이 됩니다. 한편 팩토리얼 연산의 성질에 의해 $n!>\sqrt{2πn}(n/e)^n$이라고 합니다. $n$이 1 이상일 때 $\sqrt{2πn}$ 역시 1보다 큰 값을 가지므로 여태까지 말씀드린 내용을 모두 종합해 식으로 표현하면 다음과 같습니다.
\[h\ge \log { n! } >\log { \left\{ \sqrt { 2\pi n } { \left( \frac { n }{ e } \right) }^{ n } \right\} } >\log { { \left( \frac { n }{ e } \right) }^{ n } } \\ \Rightarrow h>\log { { \left( \frac { n }{ e } \right) }^{ n } } \\ \Rightarrow h>O\left( n\log { n } \right)\]최종 도출된 부등식의 의미는 이렇습니다. 두 값을 반복적으로 비교해 정렬하는 기법인 comparison sort는 아무리 알고리즘을 잘 짜도 계산복잡성이 $O(n\log{n})$보다 크다는 말입니다. 바꿔 말해 comparison sort 계산복잡성의 하한은 $O(n\log{n})$입니다. 예컨대 퀵 정렬(quick sort)의 계산복잡성이 $O(n^2)$이고, 힙 정렬(heap sort)이 $O(n\log{n})$이라는 점을 감안하면 이같은 내용이 들어맞음을 확인할 수 있습니다.
이 글에서 설명할 counting sort는 non-comparison sort 기법으로 정렬에 드는 계산복잡성을 $O(n)$으로 낮추려는 알고리즘입니다.
counting sort
다음과 같은 입력어레이(input array) $A$에 대해 counting sort를 수행한다고 칩시다.
$A=[2,0,2,0,4,1,5,5,2,0,2,4,0,4,0,3]$
$A$의 모든 요소값의 빈도를 세어 카운팅어레이(counting array) $C$에 저장해 둡니다. $C$의 첫번째 요소 $c_1$이 3라는 5은 $A$ 가운데 0이 다섯 개 있다는 뜻입니다. 마찬가지로 $c_2$가 1이라는 말은 $A$에 1이 하나 있다는 말이 됩니다.
$C=[5,1,4,1,3,2]$
$C$의 각 요소값에 직전 요소값을 더해서 업데이트해 줍니다. 예컨대 $c_2$는 $c_1$(5)에 기존 $c_2$(1)를 더해서 만듭니다.
$C=[5,6,10,11,14,16]$
입력어레이와 같은 크기를 갖는 출력어레이(output) $B$를 만듭니다. 처음에는 비어 있습니다. 여기에서 바로 위의 $C$의 의미는 이렇습니다.
- $c_1=5$ : 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지한다.
- $c_2=6$ : 1은 $b_6$ 한 개 자리를 차지한다.
- $c_3=10$ : 2는 $b_7$에서 $b_{10}$까지 네 개 자리를 차지한다.
- $c_4=11$ : 3은 $b_{11}$ 한 개 자리를 차지한다.
- $c_5=14$ : 4는 $b_{12}$에서 $b_{14}$까지 두 개 자리를 차지한다.
- $c_6=16$ : 5는 $b_{15}$에서 $b_{16}$까지 두 개 자리를 차지한다.
| $b_1$ | $b_2$ | $b_3$ | $b_4$ | $b_5$ | $b_6$ | $b_7$ | $b_8$ |
|---|---|---|---|---|---|---|---|
| $b_9$ | $b_{10}$ | $b_{11}$ | $b_{12}$ | $b_{13}$ | $b_{14}$ | $b_{15}$ | $b_{16}$ |
이제 $A$ 요소값의 역순으로 $B$에 채워 넣습니다. 3은 $b_{11}$ 한 개 자리를 차지하므로 여기에 넣습니다. 아래와 같습니다. 이제 $b_{11}$의 자리가 채워졌으므로 $c_3$의 현재값(11)에서 1을 뺍니다.
| $b_1$ | $b_2$ | $b_3$ | $b_4$ | $b_5$ | $b_6$ | $b_7$ | $b_8$ |
|---|---|---|---|---|---|---|---|
| $b_9$ | $b_{10}$ | $b_{11}$ | $b_{12}$ | $b_{13}$ | $b_{14}$ | $b_{15}$ | $b_{16}$ |
| 3 |
다음은 0을 넣을 차례입니다. 0은 $b_1$에서 $b_5$까지 다섯 개 자리를 차지하므로 $b_5$에 넣습니다. 아래와 같습니다. 이제 $b_{5}$의 자리가 채워졌으므로 $c_1$의 현재값(5)에서 1을 뺍니다.
| $b_1$ | $b_2$ | $b_3$ | $b_4$ | $b_5$ | $b_6$ | $b_7$ | $b_8$ |
|---|---|---|---|---|---|---|---|
| 0 | |||||||
| $b_9$ | $b_{10}$ | $b_{11}$ | $b_{12}$ | $b_{13}$ | $b_{14}$ | $b_{15}$ | $b_{16}$ |
| 3 |
이러한 방식으로 $A$의 모든 요소값을 $B$에 넣으면 다음과 같이 정렬이 종료됩니다.
| $b_1$ | $b_2$ | $b_3$ | $b_4$ | $b_5$ | $b_6$ | $b_7$ | $b_8$ |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 2 | 2 |
| $b_9$ | $b_{10}$ | $b_{11}$ | $b_{12}$ | $b_{13}$ | $b_{14}$ | $b_{15}$ | $b_{16}$ |
| 2 | 2 | 3 | 4 | 4 | 4 | 5 | 5 |
두 값을 비교하는 과정 없이 정렬이 수행됐음을 확인할 수 있습니다.
파이썬 구현
카운팅 정렬을 파이썬으로 구현한 코드는 다음과 같습니다.
# A: input array
# k: maximum value of A
def counting_sort(A, k):
# B: output array
# init with -1
B = [-1] * len(A)
# C: counting array
# init with zeros
C = [0] * (k + 1)
# count occurences
for a in A:
C[a] += 1
# update C
for i in range(k):
C[i+1] += C[i]
# update B
for j in reversed(range(len(A))):
B[C[A[j]] - 1] = A[j]
C[A[j]] -= 1
return B
counting sort의 복잡성
데이터 개수가 $n$일 때 $A$의 빈도를 세는 계산복잡성은 $O(n)$입니다. 데이터 전체를 한번씩 훑어야 하기 때문입니다. 출력어레이 $B$를 만들 때도 $O(n)$입니다. $A$의 요소값들을 역순으로 모두 훑어야 하기 때문입니다.
한편 $k$는 $A$의 요소값 가운데 최댓값을 가리킵니다. 위 예시에서는 $k=5$였습니다. 카운팅어레이 $C$를 만들 때 $k+1$개의 요소값을 0으로 초기화하게 되므로 공간복잡성은 $O(k)$가 됩니다. 또한 $C$를 업데이트할 때 반복문이 $k$번 돌게 되므로 계산복잡성 또한 $O(k)$가 됩니다. 그런데 $A$가 만약 다음과 같다면 카운팅어레이 $C$의 크기가 10000+1이 되고, 반복문 또한 10000회를 돌게 되어 대단히 비효율적이게 됩니다.
$A=[0, 10000]$
요컨대 counting sort의 전체적인 계산복잡성은 $O(n+k)$가 되는데요. $k$가 충분히 작을 경우 $O(n)$이 되겠지만, $k$값이 커질 경우 $k$가 counting sort의 복잡성을 지배하게 됩니다.
Radix sort
입력데이터 $A$의 최대값인 $k$가 커지면 counting sort의 효율성은 크게 떨어집니다. 하지만 각각의 자릿수를 기준으로 정렬을 하게 되면 계산복잡성을 낮출 수 있습니다. 예컨대 10진법으로 표기된 숫자를 정렬한다면 $k$는 9가 됩니다. 이러한 정렬 방식을 Radix sort라고 합니다.
단 여기에서 주의할 것은 각 자릿수를 기준으로 정렬할 때 정렬 대상 숫자들의 위치가 뒤바뀌지 않는 stable sort 알고리즘을 적용해야 한다는 것입니다. 특정 자릿수를 놓고 정렬할 때 그 위치가 바뀌게 되면 해당 숫자가 아예 다른 숫자가 되어버리기 때문입니다. 예컨대 unstable sort를 적용하면 다음과 같은 엉뚱한 결과가 나올 수 있습니다.
14, 21 ==> 11, 24
radix sort를 연결리스트(linked list)로 구현할 수도 있습니다. 10진수 첫번째 자리를 기준으로 정렬한 뒤, 두번째 자리를 기준으로 정렬합니다. 정렬 순서를 유지하기 위해 연결리스트 삽입시 head에 넣지 않고 tail에 삽입하는 것이 특징입니다. 예컨대 아래 그림과 같이 12가 이미 있는 2번 버킷에, 22를 삽입하는 경우 12 앞이 아니라 뒤에 넣습니다. 다음 그림과 같습니다.
counting sort를 바탕으로 raddix sort를 구현한 파이썬 코드는 다음과 같습니다. counting sort도 대표적인 stable sort입니다.
# 현재 자릿수(d)와 진법(base)에 맞는 숫자 변환
# ex) 102, d = 1, base = 10, : 2
def get_digit(number, d, base):
return (number // base ** d) % base
# 자릿수 기준으로 counting sort
# A : input array
# position : 현재 자릿수, ex) 102, d = 1 : 2
# base : 10진수라면 base = 10
def counting_sort_with_digit(A, d, base):
# k : ex) 10진수의 최대값 = 9
k = base - 1
B = [-1] * len(A)
C = [0] * (k + 1)
# 현재 자릿수를 기준으로 빈도수 세기
for a in A:
C[get_digit(a, d, base)] += 1
# C 업데이트
for i in range(k):
C[i + 1] += C[i]
# 현재 자릿수를 기준으로 정렬
for j in reversed(range(len(A))):
B[C[get_digit(A[j], d, base)] - 1] = A[j]
C[get_digit(A[j], d, base)] -= 1
return B
다음은 Radix sort 코드입니다.
from math import log
def radix_sort(list, base=10):
# 입력된 리스트 가운데 최대값의 자릿수 확인
digit = int(log(max(list), base) + 1)
# 자릿수 별로 counting sort
for d in range(digit):
list = counting_sort_with_digit(list, d, base)
return list
Radix sort의 계산복잡성을 따져보겠습니다. counting sort이 $O(n+k)$이고 10진수를 예로 들 때 $k$는 9에 불과하므로, 특정 하나의 자릿수를 기준으로 counting sort하는 데 드는 비용은 $O(n)$이 될 것입니다. 그런데 전체 자릿수가 $d$라면 이를 $d$번 수행해야할 것입니다. 따라서 전체적인 복잡성은 $d×O(n)$이 됩니다. 1조($=10^{12}$)가 넘는 큰 숫자가 끼어 있어도 $d$는 12에 불과하기 때문에 선형시간에 가깝게 정렬을 수행할 수 있습니다.
Comments