계수 정렬(퍼옴)

 * Created on 2006-09-02
 *
 *  계수정렬(counting sort)은 입력키가 어떤 범위, 예를 들어 0부터 k사이의
 *  작은 정수범위에 있다는 것을 알고 있을 때만 적용할 수 있는 방법이다.
 *  이럴 때 어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에
 *  나타나는지를 알면 결정할 수 있다.
 *  예를 들어 입력키들이 숫자일 때 입력에 10이라는 키가 있고 이보다 작은
 *  키가 5개 있다면 10은 정렬순서에서 6번째에 위치하게 될 것이다.
 *  따라서 계수정렬에서는 입력 키들이 범위 k내의 각 값에 대하여 입력키가
 *  실제로 입력에 나타나는 횟수를 계산한다.
 * 
 *  예를 들어 입력키이 배열 A가
 *
 *  INDEX 0 1 2 3 4 5 6 7 8 9
 *     A     0 2 0 3 4 4 3 0 3 1
 *
 *  인 경우 키의 범위는 [0..4]이다.
 *  이 범위내의 각 숫자가 나타나는 횟수를 배열N에 나타낸다고 하면
 * 
 *  INDEX 0 1 2 3 4 
 *     N     3 1 1 3 2   : 키(숫자)의 출현횟수
 * 
 *  로 된다. 이 값은 배열 N를 0으로 초기화하고 배열 A의 각 원소 A[i]에 대하여
 *
 *  N[A[i]]  <--  N[A[i]] + 1  을 수행한 결과이다. 
 * 
 *  배열 A의 정렬된 결과는 배열 N의 값을 순서대로 읽어가면서 쉽게 구할 수 있다.
 *  예를 들어 N[0]은 3, N[1]은 1, N[2]는 1, N[3]은 3, N[4]는 2이므로
 *  이를 해석하면 0이 3개, 1이 1개, 2가 1개, 3이 3개, 4가 2개가 되므로,
 *  배열 A의 정렬 결과는 다름과 같이 간단히 구할 수 있다.
 * 
 *  0 0 0 1 2 3 3 3 4 4
 * 
 *  그러나 우리가 진정으로 구하려는 것은 키만의 정렬 순서가 아니라 키값으로
 *  대표되는 레코드들의 정렬된 순서이다. 따라서 단순한 키값의 정렬 순서가 아니라
 *  배열 A의 원소들을 직접 이동하여 얻어지는 정렬 순서가 중요하다.
 *  이를 위해서는 먼저 배열 N의 각 원소들에 대한 누적합을 구한다.
 * 
 *  INDEX 0 1 2 3 4 
 *     N     3 4 5 8 10  
 * 
 *  여기서 배열 N원소 N[j]의 값은 j가 위치할 정렬된 최대위치이다.
 *  예를 들어 키가 3인 원소는 6,7,8번째 위치를 차지한다.
 *  그러면 실제로 이것을 이용하여 정렬된 결과를 어떻게 구하는지 알아보자.
 * 
 *  여기서 정렬된 결과는 배열 B에 저장한다고 하면
 *  우선 A의 끝 원소로 부터 배열 B의 정렬위치에 저장하도록 한다.
 *  A[9] 는 1 이고 N[1]은 4이므로(네번째 위치, 인덱스로는 3) B[3]에 A[9](=1)을
 *  넣으면 된다.
 *
 *  즉 B[N[A[9]]-1]  <--  A[9] 를 실행하면 된다.
 *  이와 아울러 N[A[9]]  <-- N[A[9]] - 1을 행한다. 
 *  이 결과 N과 B의 값은 각각 다음과 같이 된다.
 * 
 *  INDEX 0 1 2 3 4 
 *     N     3 3 5 8 10  
 * 
 *  INDEX 0 1 2 3 4 5 6 7 8 9
 *     B              1              
 * 
 *  계속해서 A[8] 는 3 이고 N[3]은 8이므로(인덱스로는 7) B[7]에 A[8](=3)을 넣고
 *  아울러 N[A[8]]  <-- N[A[8]] - 1을 행한다.
 * 
 *  이에 대한 결과 N과 B의 값은
 * 
 *  INDEX 0 1 2 3 4 
 *     N     3 3 5 7 10  
 * 
 *  INDEX 0 1 2 3 4 5 6 7 8 9
 *     B              1         3     
 * 
 * 이상의 과정을 나머지에 대해 반복하면 정렬된 결과를 얻을 수 있다.
 * 
 * 이 알고리즘의 시간 복잡도는 O(n + k)이다.
 * 글런데 계수 정렬은 보통 k=O(n)일 때에만 사용되므로
 * 실질적으로는 시간복잡도가 O(n)이라고 할 수 있다.
 *
 * 계수정렬의 한가지 중요한 성질은 동일한 키의 상대적 순서가 바뀌지 않는
 * 안정적 정렬이라는 것이다.
 *
 *   (이지수, 김명, 조유근, 홍영식 지음.  이한출판사 '알고리즘' 에서 인용)