8 Sorting in Linear Time

우리는 이제 $O(n \; lg\; n)$시간에 n개의 숫자들을 정렬할 수 있는 몇 가지 알고리즘들을 소개했다. Merge sort와 hearpsort는 worst case에 이 upper bound에 도달한다; quicksort는 그것을 평균적으로 도달한다. 게다가, 이러한 알고리즘들 각각에 대해, 우리는 그 알고리즘이 $\Omega(n \; lg \;n)$ 시간에 작동하도록 하는 n개의 input 숫자들의 수열을 만들 수 있다.

​ 이러한 알고리즘들은 흥미로운 특성을 공유한다 : 그것들이 결정하는 정렬된 순서는 input elements사이의 비교에만 기반으로 한다. 우리는 그러한 sorting algorithms을 comparison sorts라고 부른다. 따라서 이제까지 소개된 모든 정렬 알고리즘들은 비교 정렬이다.

​ Section 8.1에서, 우리는 어떤 비교 정렬은 n개의 elements를 정렬하기 위해 worst case에서 $\Omega(n \; lg \;n)$ 비교를 해야만 한다고 증명할 것이다. 따라서, merge sort와 heapsort는 asymptotically optimal이고, 상수 요소에 의해 더 빠른 어떠한 비교 알고리즘도 존재하지 않는다.

​ Section 8.2, 8.3, 그리고 8.4는 세 개의 정렬 알고리즘들을 조사한다 - counting sort, radix sourt, 그리고 butket sort - linear time에 작동하는. 물론, 이러한 알고리즘들은 sorted order를 결정하기 위해 비교보다는 다른 연산을 사용한다. 결과적으로, 그 $\Omega(n \; lg \; n)$ lower bound는 그것들에게 적용되지 않는다.

8.1 Lower bounds for sorting

비교 정렬에서, 우리는 input sequence $\langle a_1, a_2, \dots , a_n \rangle$에 대한 순서 정보를 얻기위해 elements사이의 비교만을 사용한다. 즉, 두 개의 원소 $a_i$와 $a_j$가 주어진다면, 우리는 그것들의 상대 순서를 결정하기 위해, $a_i < a_j,\;\; a_i \leq a_j,\;\; a_i = a_j, \;\; a_i \geq a_j,\;\; a_i > a_j$ 테스트 들 중 하나를 수행한다. 우리는 어떤 다른 방법으로 그 elemtns의 값을 조사하지 않거나, 그것들에 대한 순서 정보를 얻지 않을지도 모른다.

​ 이 섹션에서, 우리는 모든 input elements가 다르다는 일반성의 손실 없이 갖어한다. 이 가정이 주어진다면, $a_i = a_j$의 형태의 비교들은 쓸모없다. 그래서 우리는 이러한 형태의 어떠한 비교도 만들어지지 않는다고 가정할 수 있다. 우리는 또한 $a_i < a_j,\;\; a_i \leq a_j,\;\;a_i \geq a_j,\;\; a_i > a_j$ 비교들이 모두 같다는 것에 유의한다. 그것들이 $a_i$와 $a_j$에 대한 상대 순서에 대해 동일한 정보를 만든다는 점에서 그렇다. 우리는 그러므로 모든 비교는 $a_i \leq a_j$의 형태를 갖는다고 가정한다.

The decision-tree model

우리는 의사 결정 트리의 관점에서 비교 정렬를 추상적으로 볼 수 있다. decision tree는 주어진 사이즈의 입력에 대해 작동하는 특별한 정렬 알고리즘에 의해 수행되는 elements 사이의 비교를 나타내는 full binary tree이다. 알고리즘의 Control, data movement, 그리고 모든 다른 측면들은 무시된다. 그림 8.1은 세 개의 elements의 input sequence에 작동하는 Section 2.1의 insertion sort algorithm과 대응되는 의사결정 트리를 보여준다.

​ 한 decision tree에서, 우리는 범위 $1 \leq i, \;j \leq n$에서 어떤 $i$와 $j$에 대해 $i:j$로 각 internal node에 주석을 단다. 거기에서 n은 input sequence에서의 elements의 개수이다. 우리는 또한 각 leaf를 permutation $\langle \pi(1), \pi(2), \dots, \pi(n) \rangle$로 표기한다. (permutations에 대한 배경을 위한 Section C.1를 보아라.) sorting algorithm의 실행은 decision tree의 root에서 leaf로 가는 간단한 경로를 추적하는 것과 대응된다. 각 internal node는 $a_i \leq a_j$의 비교를 가리킨다. 그 left subtree는 그러고나서 $a_i \leq a_j$인 것을 알고난다면, 이후의 비교를 말한다. 그리고, right subtree는 $a_i > a_j$인 것을 아는 이후의 comparisons을 말한다. leaf에 대해서, 그 sorting algorithm은 $a_{\pi(1)} \leq a_{\pi(2)} \leq \cdots \leq a_{\pi(n)}$의 순서를 만들어낸다. 어떤 올바른 정렬 알고리즘은 그것의 입력에 대해 각 permutation을 생산할 수 있어야 하기 때문에, n개의 elements에 대해 n! permutations의 각각은 비교 정렬이 올바르게 되기 위해 그 decision tree의 leaf들 중 하나로 나타나야 한다. 게다가, 이러한 leaf들 각각은 root에서 아래쪽 경로로 닿을 수 있어야 한다. 이것은 실제 비교 정렬의 실행과 일치한다. (우리는 그러한 leaves를 "reachable"하다고 지칭한다.) 따라서, 우리는 각 permutation이 reachable lef로서 나타나는 decision trees만을 고려할 것이다.

A lower bound for the worst case

한 decision tree의 root에서 그것의 reachable leaves 중 어떤 것으로 가는 가장 긴 simple path의 길이가, 그 대응되는 정렬 알고리즘이 수행하는 비교의 worst-case number를 나타낸다. 결과적으로, 주어진 비교 정렬 알고리즘을 대해 worst-case 비교 횟수는 그것의 decision tree의 높이와 같다. 각 permutation이 reachable leaf로서 나타나는 모든 decision tree의 높이에 대한 lower bound는 그러므로, 어떤 비교 정렬 알고리즘의 작동시간의 lower bound이다. 다음의 정리는 그러한 lower bound를 만든다.

Theorem 8.1

어떤 비교 정렬 알고리즘은 worst case에서 $\Omega(n \; lg \; n)$을 요구한다.

Proof

앞의 이야기로부터, 각 permutation이 reachable leaf로서 나타나는 decision tree의 높이를 결정하는 것으로 충분하다. n개의 elements에 비교정렬과 대응되는 l개의 reachable leaves를 가진 h의 높이의 decision tree를 고려해라. 그 입력에 대한 n! permutations의 각각은 어떤 leaf로서 나타나기 때문에, 우리는 $n! \leq l$ 를 가진다. height h의 binary tree는 $2^h$ 이상의 leaves를 가질 수 없기 때문에, 우리는 다음을 가지게 된다
$n! \leq l \leq 2^h$
그리고, 로그를 적용하여, 다음을 암시한다
$h \geq lg(n!) \;\; \text{(since the lg function is monotonically increasing)} \\ = \Omega(n \;lg \; n) \;\; \text{(by equation (3.19)).}$

Corollary 8.2

Heapsort와 merge sort는 asmptotically optimal comparison sorts이다.

Proof

heapsort와 merge sort에 대한 그 $O(n\;lg\;n)$ upper bounds는 Theorem 8.1로부터의 $\Omega(n\;lg\;n)$ worst-case lower bound와 부합한다.

8.2 Couting sort

Counting sort는 어떤 정수 k에 대해 n개의 input elements의 각각이 0부터 k까지의 범위에 있는 정수라고 가정한다. $k = O(n)$일 때, 그 정렬은 $\Theta(n)$ time에 작동한다.

​ Couting sort는 각 input element x에 대해, x보다 더작은 elements의 개수를 결정한다. 그것은 element x를 직접적으로 output array에 있는 그것의 위치에 놓기 위해 이 정보를 사용한다. 예를들어, 만약 17개의 elements가 x보다 더 작다면, 그러면 x는 output position 18에 속한다. 우리는 몇 가지 elements들이 같은 값을 가지는 상황을 처리하기 위해 이 전략을 다소 수정해야만 한다. 왜냐하면 우리는 그것들 모두를 같은 위치에 넣기를 원하지 않기 때문이다.

​ counting sort를 위한 코드에서, 우리는 그 input이 array $A[1..n]$이라고 하고, 따라서 $A.length = n$이라고 가정한다. 우리는 두 개의 다른 배열들을 요구한다 : 그 배열 $B[1..n]$은 정렬된 output을 가지고, 그 배열 $C[0..k]$는 임시 작업공간을 제공한다.

COUNTING-SORT(A, B, k)
1	let C[0..k] be a new array
2	for i = 0 to k
3		C[i] = 0
4	for j = 1 to A.length
5		C[A[j]] = C[A[j]] + 1
6	// C[i] now contains the number of elements equal to i
7	for i = 1 to k
8		C[i] = C[i] + C[i - 1]
9	// C[i] now contains the number of elements less than or equal to i.
10	for j = A.length down to 1
11		B[C[A[j]]] = A[j]
12		C[A[j]] = C[A[j]] - 1

그림 8.2는 counting sort를 보여준다. lines 2-3의 for loop가 배열 C를 모두 0으로 초기화 한 후에, lines 4-5의 for loop가 각 input element를 검사한다. 만약 input element의 그 값이 i라면, 우리는 C[i]를 증가시킨다. 따라서, line 5이후에, C[i]는 각 정수 $i = 0,1, \dots,k$에 대해, i와 같은 input elements의 개수를 가진다. Lines 7-8은 각 $i = 0,1,\dots,k$에 대해, array C의 sum을 계속 유지하여, i와 같거나 작은 elements들이 얼마나 많은지를 결정한다.

​ 마지막으로, lines 10-12의 for loop는 각 element A[j]를 output array B에 있는 올바른 정렬된 위치에 넣는다. 만약 모든 n개의 원소들이 다르다면, 그러면 우리가 line 10에 도달할 때, 각 A[j]에 대해, 그 값 C[A[j]]는 output array애서 A[j]의 올바른 최종 포지션에 있게 된다. 왜냐하면 A[j]와 같거나 더 작은 C[A[j]] elements들이 있기 때문이다. 그 elements들이 다르지 않을 수도 있기 때문에, 우리는 우리가 A[j]를 B array에 놓을 때 마다 C[A[j]]를 감소시킨다. C[A[j]]를 감소시키는 것은 A[j]와 같은 값을 가진 다음 input element가 output array에 A[j]이전의 자리로 즉시 가도록 한다 만약 그것이 존재한다면.

​ counting sort는 얼마나 많은 시간을 요구하는가? lines 2-3의 for loop는 $\Theta(k)$의 시간이 걸리고, lines 4-5의 for loop는 $\Theta(n)$의 시간이 걸리고, lines 7-8의 for loop는 $\Theta(k)$의 시간이 걸리고, 10-12의 for loop는 $\Theta(n)$의 시간이 걸린다. 따라서, 전체 시간은 $\Theta(k + n)$이다. 실제로, 우리는 보통 우리가 $k = O(n)$일 때 counting sort를 사용한다. 그리고 이 경우에 그 running time은 $\Theta(n)$이다.

​ Counting sort는 Section 8.1에서 제공되는 $\Omega(n \; lg \; n)$ lower bound를 이긴다. 왜냐하면 그것은 comparison sort가 아니기 때문이다. 사실, input elements사이의 어떠한 비교도 코드에서 발생하지 않는다. 대신에, counting sort는 한 array에 index하기 위해 elements의 실제 값을 사용한다. 정렬에 대한 그 $\Omega(n\;lg\;n)$ lower bound는 우리가 comparison sort model에서 떠날 때 적용되지 않는다.

​ counting sort의 중요한 특징은 이것이 stable 하다는 것이다 : 같은 값을 가진 숫자들은 그것들이 input array에 있는 것과 같은 순서로 output array에 나타난다. 즉, 그것은 어떤 숫자들이 그 input array에 처음 나타나든 output array에 처음 나타난다는 규칙에 의해 두 숫자 사이의 연결고리를 없앤다. 일반적으로, stability의 특징은 satellite data가 정렬될 element와 함께 이동할 때만 중요하다. Counting sort의 stability는 또 다른 이유로 중요하다: counting sort는 종종 radix sort의 subroutine으로서 사용된다. 우리가 그 다음 섹션에서 보게 되듯이, radix sort가 정확히 작동하기 위해서, counting sort는 stable해야만 한다.

8.3 Radix sort

Radix sort는 너가 이제 컴퓨터 박물관에서만 찾을 수 있는 card-sorting machines에 의해 사용되는 정렬이다. 그 cards는 80개의 columns을 가지고 있고, 각 column에서, 한 machine은 12개의 장소들 중 하나에 구멍을 뚫을 수 있다. 그 sorter는 기계적으로 프로그래밍 되어질 수 있는데, 한 deck에 있는 각 card의 주어진 column을 조사하고, 어떤 장소가 뚫렸는지에 따라 그 카드를 12개의 bins중의 하나로 분배하기 위해서이다. 한 operator는 그러고나서 bin별로 cards를 모을 수 있고, 첫 번째 장소에 뚫리게 된 카드들은 두 번째 뚫린 카드들 위에 있게 된다.

​ decimal digits에 대해, 각 column은 오직 10개의 장소들만 사용한다 (다른 두 개의 장소들은 nonnumeric characters를 encoding을 위해 유보된다.) d-digit number는 그러고나서 d번째 columns의 field를 차지할 것이다. 그 card sorter는 한 번에 오직 한 개의 column을 볼 수 있기 때문에, d-digit number에 대한 n개의 카드를 정렬하는 문제는 sorting algorithm을 요구한다.

​ 직관적으로, 너는 그것들의 most significant digit으로 숫자들을 정렬하고, 그 최종 bins 각각을 재귀적으로 정렬하고, 그러고나서 순서대로 decks를 합칠지도 모른다. 불행하게도, 10개의 bins중 9개에 있는 cards들은 그 bins의 각각을 정렬하기 위해 옆으로 제쳐둬야 하기 때문에, 이 절차는 너가 추적해야만 하는 카드들의 많은 중간 더미들을 생성한다.

​ Radix sort는 least significant digit를 처음에 정렬하여 -비직관적으로- card sorting의 문제를 해결한다. 그 알고리즘은 그러고나서 그 카드들을 단일의 deck에 합치는데, 0번째 bin의 카드들이 1번째 bin의 cards들을 선행하고, 1번째 bin의 카드들은 2번째 bin의 카드들에 선행한다. 그러고나서, 그것은 second-least significant digit으로 다시 전체 deck을 정렬하고, 그 deck을 같은 방식으로 재조합한다. 그 프로세스는 그 카드들이 모든 d digits에 대해 정렬될 때 까지 계속한다. 놀랍게도, 그 시점에, 그 카드들은 d-digit number에 대해 완전히 정렬된다. 따라서, 오직 그 deck를 통한 d번의 passes들이 정렬하기 위해 요구된다. 그림 8.3는 radix sort가 7개의 3-digt numbers의 "deck"에 어떻게 작동하는지를 보여준다.

​ radix sort가 정확하게 작동하기 위해서, 그 digit sorts는 stable해야마 ㄴ한다. 한 card sorter에 의해 수행되는 정렬이 stable하지만, 그 operator는 비록 한 bin에 있는 모든 카드들이 선택된 column에서 같은 digit를 가지고 있을지라도, bin에서 그것들이 나올 때, 그 카드들의 순서를 바꾸지 않도록 경계해야만 한다.

​ 순차적 random-access machine인 일반 컴퓨터에서, 우리는 가끔씩, 여러개의 fields로 keyed되어지는 정보의 records들을 정렬하기 위해 radix sort를 사용한다. 예를들어, 우리는 세 개의 keys로 날짜를 정렬하기를 원할지도 모른다 : year, month, and day. 우리는 두 개의 날짜가 주어진다면, 년을 비교하고, 그리고 tie가 있다면 months를 비교하고, 또 다른 tie가 발생하면 dayts를 비교하는 비교 함수로 정렬 알고리즘을 작동시킬 수 있다. 대안적으로, 우리는 한 stable sort로 세 번 그 정보를 정렬할 수 있다: 처음에는 day, 그 다음으로는 month, 마지막으로 year.

​ radix sort를 위한 코드는 간단하다. 다음의 절차는 n-element array A에 있는 각 element가 d digits를 가진다고 가정한다. 거기에서 digit 1은 lowest-order digit이고, digit d는 highst-order digit이다.

RADIX-SORT(A, d)
1	for i = 1 to d
2		use a stable sort to sort array A on digit i

Lemma 8.3

각 digit이 k까지 가능한 값을 취할 수 있는, 값n개의 d-digit numbers가 주어진다면, RADIX-SORT는 이러한 숫자들을 $\Theta(d(n + k))$ 시간에 이러한 숫자들을 정확하게 정렬한다. 만약 그것이 사용하는 stable sort가 $\Theta(n + k)$ time이 걸린다면.

Proof

radix sort의 올바름은 정렬되어질 column의 귀납법을 따른다 (Exercise 8.3-3 참조). 그 작동시간에 대한 분석은 중간 sorting algorithm로서 사용되는 stable sort에 의존한다. 각 digit이 0 ~ k-1의 범위에 있을 때 (그것이 k개의 가능한 값을 취할 수 있게 하기 ㅜ이해), 그리고 k가 너무 크지않을 때, counting sort는 명확한 선택이다. n개의 d-digit 숫자들에 대해 각 pass는 그러면 $\Theta(n + k)$가 걸린다. d개의 passes들이 있고, radix sort에 대한 전체 시간은 $\Theta(d(n + k))$이다.

​ d가 상수이고, $k = O(n)$ 일 때, 우리는 radix sort가 linear time에 작동하도록 만들 수 있다. 좀 더 일반적으로, 우리는 각 key를 digits으로 분해하는 방법에 어떤 유연성을 가진다.

Lemma 8.4

n개의 b-bit numbers와 어떤 양의 정수 $r \leq b$가 주어진다면, RADIX-SORT는 올바르게 이러한 숫자들을 $\Theta((b/r)(n + 2^r))$ 시간에 정렬한다. 만약 그것이 사용하는 stable sort가 0~k의 범위에 있는 입력들에 대해 $\Theta(n + k)$가 걸린다면.

Proof

$r \leq b$인 값에 대해, 우리는 각 key를 각각 r개의 bits의 $d = \lceil b/r \rceil$를 가지는 것으로서 본다. 각 digit은 0 ~ $2^r - 1$의 범위에 있는 정수이고, 우리가 $k = 2^r - 1$로 counting sort를 사용할 수 잇게 하시 위해서이다. (예를들어, 우리는 32-bit word를 4개의 8-bit digits을 가지는 것으로 보는데, $b = 32, r = 8, k = 2^r - 1 = 255, and\; d = b/r = 4.$) counting sort의 각 pass는 $\Theta(n + k) = \Theta(n + 2^r)$의 시간이 걸리고, $\Theta(d(n+2^r)) = \Theta((b/r)(n + 2^r))$의 총 작동시간을 위해 d개의 passes들이 있다.

n과 b의 주어진 값들에 대해, 우리는 r의 값을 $r \leq b$로 선택하기를 원한다. 이것은 $(b/r)(n+2^r)$ 식을 최소화하는 값이다. 만약 $b < \lfloor lg\;n\rfloor$이라면, 그러면 $r \leq b$인 어떤 값에 대해, 우리는 $(n + 2^r) = \Theta(n)$을 갖게 된다. 따라서, $r = b$를 선택하느 ㄴ것은 $(b/b)(n + 2^b) = \Theta(n)$의 작동 시간을 만든다. 그리고 이것은 asymptotically optimal이다. 만약 $b \geq \lfloor lg\;n \rfloor$이라면, 그러고나서 $r = \lfloor lg\; n \rfloor$를 선택하는 것은 constant factor내에서 우리가 다음과 같이 볼 수 있는 최상의 식나을 준다. $r = \lfloor lg \; n \rfloor$를 선택하는 것은 $\Theta(bn / lg\;n)$의 작동시간을 만든다. 우리가 $\lfloor lg\;n \rfloor$위로 r를 증가시킨다면, 분자에 있는 $2^r$ 항은 분모에 있는 $r$ 항보다 더 빠르게 증가하고, 그래서 $\lfloor lg\;n \rfloor$위로 r를 증가시키는 것은 $\Omega(bn/lg\;n)$의 작동 시간을 만든다. 만약 대신에 우리가, $\lfloor lg \; n \rfloor$ 아래로 r를 감소시키려고 한다면, 그러면 $b/r$항은 증가하고, $n + 2^r$항은 $\Theta(n)$으로 남게된다.

​ radix sort는 quick sort같은 비교 기반의 정렬 알고리즘보다 더 선호되는가? 만약 $b = O(lg\;n)$라면, 종종 그렇듯이, 우리는 $r \approx lg;n $는 선택한다. 그러고나서 radix sort의 작동시간은 $\Theta(n)$이고, 이것은 quicksort의 예상되는 작동 시간인 $\Theta(n \; lg\; n)$보다 더 좋은 것처럼 보인다. 그러나, $\Theta$-notation에 숨겨진 상수 요소들은 다르다. 비록 radix sort가 n개의 keys에 대해 quicksort보다 더 적은 passes들을 만들지도 모르지만, radix sort의 각 pass는 상당히 더 오래 걸릴지도 모른다. 우리가 어떤 정렬 알고리즘을 선호하는지는 구현, 기저의 머신, 그리고 input data의 특징에 의존한다 (예를들어, quicksort는 종종 radix sort보다 하드웨어 캐시를 좀 더 효과적으로 사용한다). 게다가, counting sort를 중간 stable sort로서 사용하는 radix sort의 버전은 제자리에서 정렬하지 않는다. 그리고 많은 $\Theta(n\;lg\;n)$ time의 비교 정렬은 그렇게 한다. 따라서, primary memory storage가 부족하다면, 우리는 quicksort같은 in-place algorithm을 선호할지도 모른다.

---

Radix Sort 구현

위의 설명의 알고리즘에 따라, bit별로 비교하여 정렬하는 구현을 찾기 힘들어 직접 구현했다. 백준 문제 2751 수 정렬하기 2에서 그것을 구현해서 풀었다. 다음은 그 코드이고, 설명은 주석에 달아 놓았다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

int main(void)
{
	int N;
	scanf("%d", &N);
    // input과 output을 위한 용도로 N * 2의 메모리할당.
	int* root = (int*)malloc(sizeof(int) * N * 2);

    // input/output pointer 할당
	int* input = root;
	int* output = &input[N];
    
    // 음수가 있을 수 있기 때문에, counting sort를 적용하기 위해
    // 1,000,000(100만)을 추가하여, 0 ~ 2,000,000(200만)의 범위로 만듬.
	for (int i = 0; i < N; ++i)
	{
		int numb;
		scanf("%d", &numb);

		input[i] = numb + 1000000;
	}

    // 입력 값은 int에 대해 정렬하는 것이기 때문에 다음과 같은 key compare를 한다.
    // 0xFF 		== 0000 0000 0000 0000 0000 0000 1111 1111
    // 0xFF00 		== 0000 0000 0000 0000 1111 1111 0000 0000
    // 0xFF0000		== 0000 0000 1111 1111 0000 0000 0000 0000
    // 0x7F000000	== 0111 1111 0000 0000 0000 0000 0000 0000
    // 여기에서 주의할 점이 있는데, integer bit representation의
    // most significant bit는 sign bit이기 때문에, 마지막 key에서 
    // most significant bit은 0으로 해주어야 항상 양수에 대해 우리는 비교할 수 있다.
	int keyindex = 0;
	int keycompare[4];
	keycompare[0] = 0xFF;
	keycompare[1] = 0xFF00;
	keycompare[2] = 0xFF0000;
	keycompare[3] = 0x7F000000;
    
    // 우리는 4개의 key로 비교한다.
	while (keyindex < 4)
	{
        // 비교할 key
		int key = keycompare[keyindex];
        
        // counting sort의 temporary working space
		int temp[0xFF + 1] = { 0, };

        // 해당 key value로 해당 값이 몇 개 있는지 구함.
		for (int i = 0; i < N; ++i)
		{
			int keyvalue = input[i] & key;

            // 이것을 해주는 이유는 
            // 각 key의 bit가 1개라도 &연산된다면
            // keycompare[3]의 경우
            // keyvalue값은 매우커지게 된다.
            // 따라서 temporary working space를 작게 유지하기 위해
            // 그것을 0 ~ 7 bit index의 범위로 움직여준다면
            // 우리는 temporary working space를 작게 유지할 수 있다.
            keyvalue >>= 8 * keyindex;

            // 올바른 keyvalue를 맞췄으므로 +1
			temp[keyvalue] += 1;
		}

        // counting sort의 로직에 따라
        // 자기 자신과 같거나 작은 것의 개수를 구함.
		for (int i = 1; i <= 0xFF; ++i)
			temp[i] = temp[i] + temp[i - 1];

        // 이제 최종적으로 output에 그 정렬된 결과를 써주어야 한다.
		for (int i = N - 1; i >= 0; --i)
		{
            // 위에서 설명한대로 keyvalue를 다시 구하고
			int keyvalue = (input[i] & key) >> (8 * keyindex);

            // output은 0 ~ (N - 1)이기 때문에 그 개수의 -1를 해주어야
            // 범위에 맞게 들어간다.
			output[temp[keyvalue] - 1] = input[i];
			temp[keyvalue] -= 1;
		}

		++keyindex;
        
        // Notice
        // radix sort의 특성상 계속해서 정렬시켜 나가야 하기 때문에
        // 새로운 배열을 만들기보다 input/output pointer를 swap하여
        // radix sort가 정렬된 결과에 또 정렬을 할 수 있게하고,
        // 다른 곳에 output을 적게 만든다.
		int* tempptr = input;
		input = output;
		output = tempptr;
	}

    // key index		input pointer	output pointer
    // 0 			: 	input, 			output
    // 1 			: 	output, 		input
    // 2 			: 	input, 			output
    // 3 			: 	output, 		input
    // while escape	:	input,			output
    // 3에서 input에 결과를 write한다.
    // 그리고 while문을 탈출하면서, 그 input이 input pointer에 가게된다.
    // 따라서 input pointer에 그 결과가 담겼으므로 그걸로 출력
	for (int i = 0; i < N; ++i) printf("%d\n", input[i] - 1000000);
	free(root);

	return 0;
}

---

8.4 Bucket sort

Bucket sort는 input이 uniform distribution(정규 분포)로부터 들어옥오고, $O(n)$의 평균의 작동시간을 갖는다고 가정한다. counting sort와 마찬가지로, bucket sort는 그것이 input에 대한 어떤 것을 가정하기 때문에 빠르다. counting sort가 input이 작은 범위의 integers로 구성되었다는 것을 가정하는 반면에, bucket sort는 그 input이 범위 [0, 1)의 elements를 균일하고 독립적으로 분배하는 random process에 의해 생성된다고 가정한다. (uniform distribution에 대한 정의를 위해서 C.2를 보아라.)

​ Bucket sort는 interval [0, 1)를 n개와 동일한 크기의 subintervals, 즉 buckets으로 나누고, 그러고나서 그 n개의 input numbers를 buckets으로 분배한다. 그 inputs이 균일하고 독립적으로 [0,1)에 대해 분배되기 때문에, 우리는 많은 수들이 각 bucket에 들어가는 것을 기대하지 않느다. 그 output을 만들기 위해, 우리는 간단히 그 숫자들을 각 bucket에서 정렬하고, 그러고나서 순서대로 buckets을 훑어서 그 elements를 각각에서 열거한다.

​ bucket sort를 위한 우리의 코드는 그 input이 n-element array A이고, 그 배열에 있는 각 원소 $A[i]$는 $0 \leq A[i] < 1$를 만족한다고 가정한다. 그 코드는 linked lists (buckets)의 보조 배열 $B[0..n-1]$를 요구하고, 그러한 리스트들을 유지하기위한 메커니즘이 있다고 가정한다 (Section 10.2는 linked list의 기본 연산들을 구현하는 방법을 설명한다.)

BUCKET_SORT(A)
1	let B[0..n-1] be a new array
2	n = A.length
3	for i = 0 to n -1
4		make B[i] an empty list
5	for i = 1 to n
6		insert A[i] into list B[floor(nA[i])]
7	for i = 0 to n - 1
8		sort list B[i] with insertion sort
9	concatenate the list B[0], B[1], ...., B[n - 1] together in order

그림 8.4는 10개의 숫자들의 입력 배열에 대한 bucket sort의 연산을 보여준다.

​ 이 알고리즘이 작동하는 것을 보기위해서, 두 개의 원소들 $A[i]$와 $A[j]$를 고려해라. $A[i] \leq A[j]$라는 것의 일반성의 손실 없이 가정해라. $\lfloor nA[i] \rfloor \leq \lfloor n A[j] \rfloor$이기 때문에, elemetn $A[i]$는 $A[j]$와 같은 버킷에 들어가거나, 또는 그것은 더 낮은 index를 가진 bucket에 들어간다. 만약 $A[i]$와 $A[j]$가 같은 bucket에 들어간다면, lines 7-8의 for loop는 그것들을 적절한 순서로 넣는다. 만약 $A[i]$ 와 $A[j]$가 다른 buckets에 들어간다면, 그러면 line 9가 그것들을 적절한 순서에 넣는다. 그러므로, bucket sort는 정확히 작동한다.

​ 그 작동시간을 분석하기 위해, line 8을 제외하는 모든 lines들은 worst case에서 $O(n)$ time이 걸린다. 우리는 line 8에서 insertion sort에 대한 n개의 호출에 걸리는 총 시간을 분석할 필요가 있다.

​ insertion sort에 대한 호출의 비용을 분석하기 위해, $n_i$가 bucket $B[i]$에 위치한 elements의 개수를 나타내는 random 변수라고 하자. insertion sort는 quadratic time에 작동하기 때문에 (Section 2.2참조), 그 bucket sort의 작동 시간은
$T(n) = \Theta(n) + \sum^{n - 1}_{i = 0} O(n^2_i).$
우리는 이제, bucket sort의 평균 케이스의 running time을 분석하는데, runing time의 예상되는 값을 연산하여 한다. 거기에서 우리는 input distribution에 대한 기대를 고려한다. 양변의 기대를 고려하고, expectation의 linearity를 사용하여, 우리는 다음을 갖는다
$E[T(n)] = E \left[ \Theta(n) + \sum^{n-1}_{i=0} O(n^2_i) \right] \\ = \Theta(n) + \sum^{n-1}_{i=0} E [O(n^2_i)] \;\; \text{(by linearity of expectation)} \\ = \Theta(n) + \sum^{n-1}_{i=0} O(E [n^2_i]) \;\; \text{(by equation (C.22))}. \\ (8.1)$
우리는 다음을 주장한다
$E[n^2_i] = 2 - 1/n \;\; (8.2)$
$i = 0, 1, \dots, n - 1$에 대해, 각 bucket i가 $E[n^2_i]$와 같은 값을 가진다는 것을 놀랍지 않다. 왜냐하면 그 input array A에 있는 각 값은 어떤 bucket에 든지 동일하게 들어갈 가능성이 높기 때문이다. 방정식 (8.2)를 증명하기 위해, 우리는 indicator random variables를 정의한다.
$X_{ij} = I \{ A[j] \;\; \text{falls in bucket}\;\; i\; \} \\$
$i = 0, 1, \dots, n - 1$과 $j = 1, 2, \dots, n$에 대해. 따라서,
$n_i = \sum^n_{j=1} X_{ij}.$
$E[n^2_i]$를 연산하기 위해, 우리는 그 square를 확장하고, 그 용어들을 regroup한다.
$E[n^2_i] = E \left[ \left( \sum^2_{j=1} X_{ij} \right) \right] \\ = E \left[ \sum^n_{h=1} \sum^n_{k=1} X_{ij} X_{ik} \right] \\ = E \left[ \sum^n_{j=1} X^2_{ij} + \sum_{i \leq j \leq n} \sum_{1 \leq k \leq n \\k \ne j} X_{ij} X_{ik} \right], \\ (8.3)$
여기에서 그 마지막 line은 expectation의 linearity를 따른다. 우리는 그 두 합을 별개로 구한다. Indicator random variable $X_{ij}$는 확률 $1/n$을 가진 1이고, 그렇지 않다면 0이다. 그러므로
$E[ X^2_{ij}] = 1^2 \cdot \frac{1}{n} + 0^2 \cdot (1 - \frac{1}{n}) \\ = \frac{1}{n}.$
$k \ne j$일 때. 그 변수 $X_{ij}$와 $X_{ik}$는 독립적이므로,
$E[X_{ij} X_{ik}] = E[X_{ij}] E[X_{ik}] \\ = \frac{1}{n} \cdot \frac{1}{n} \\ = \frac{1}{n^2}.$
방정식 (8.3)에서 이러한 두 개의 예상되는 값을 치환하여, 우리는 다음을 얻는다
$E[n^2_i] = \sum^n_{j=1} \frac{1}{n} + \sum_{1 \leq j \leq n} \sum_{1 \leq k \leq n \\ k \leq j} \frac{1}{n^2} \\ = n \cdot \frac{1}{n} + n(n-1) \cdot \frac{1}{n^2} \\ = 1 + \frac{n-1}{n} \\ = 2 - \frac{1}{n},$
그리고 이것은 방정식 (8.2)를 증명한다.

방정식 (8.1)에서 이 예상되는 값을 사용하여, 우리는 bucket sort에 대해 평균 경우의 작동 시간을 $\Theta(n) + n \cdot O(2 - 1/n) = \Theta(n)$으로 결론짓는다.

​ 비록 그 입력이 uniform distribution이 아닐지라도, bucket sort는 여전히 linear time에 작동할지도 모른다. bucket sizes의 제곱의 합이 elements의 총 개수에서 linear하다는 property를 input이 갖는 한, 방정식 (8.1)은 우리에게 bucket sort가 linear time에 작동할 것이라는 것을 말해준다.