[Algorithm] 3-7. Counting Sort - 선형시간 알고리즘

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

3-7. Counting Sort - 선형시간 정렬 알고리즘

• 선형시간 = O(n)

• 즉, comparison sort가 아니다.(comparison sort의 하한은 O(nlogn)이다.)

Sorting in Linear Time

Counting Sort

• n개의 정수를 정렬하라. 단 모든 정수는 0에서 k사이의 정수이다.

• 예) n명의 학생들의 시험점수를 정렬하라. 단 모든 점수는 100이하의 양의 정수이다.

• k=5인 경우의 예

  • 배열 C는 counter 배열

• code

  • A[] - 정렬할 데이터

  • C[] - counter 배열

int A[n];
int C[k] = {0, };
for (int i = 1; i <= n; i++)
  C[A[i]]++;
for (int s = 1, i = 0; i <= k; i++) {
  for (int j = 0; j < C[i]; j++) {
    A[s++] = i;
  }
}

• 대부분의 경우 정렬할 key값들은 레코드의 일부이기 때문에, 다수의 칼럼을 포함하는 레코드를 정렬하기에는 적합하지 않은 정렬 알고리즘이다.

• 따라서, 실제로 counting sort는 조금 더 복잡하게 할 수 밖에 없다.

• 위의 방법 처럼 각각의 요소를 카운팅 했더라도, 실제로는 index 4와 7에 존재하는 0을 각각 앞으로 가져오는 작업이 필요하다. 정렬할 데이터가 레코드의 일부인 key값이라고 생각하고, 함께 움직여야 할 레코드가 있는 것으로 판단한다.

• (a)단계에서 각각 요소를 카운팅 했다면,

• (b)단계에서는 각 데이터들의 누적합을 구한다. b단계에서 C배열의 인덱스 1의 값이 2인 것은 1보다 작거나 같은 원소의 갯수이다. 같은 원리로 인덱스 2 위치의 값이 4인것은 2보다 작거나 같은 원소의 갯수가 4개 이기 때문이다.(1보자 작거나 같은 원소의 수 2개, key값이 2인 원소 2개)

• 누적합을 구했다면, 주어진 배열 A를 한번에 정렬할 수 있다. A배열의 마지막 원소부터 첫번째 원소의 순으로 해당 원소가 들어갈 위치를 찾는다.

• 예를들어, (c)단계에서 A배열의 마지막 인덱스의 값인 3이 들어갈 위치를 찾으려면, 누적합을 구했던 배열 C의 3번 인덱스 값을 참조한다. 값은 7이다. 이 얘기는, 3보다 작거나 같은 원소의 수가 7이라는 이야기 이므로 정렬된 배열을 저장할 B의 7번 인덱스에 값 3이 들어가면 된다. 그리고 누적합 C배열의 3번 인덱스의 값을 6으로 1감소시킨다.

• 다음으로 A배열의 7번 인덱스 위치에 있는 값 0이 들어갈 위치를 구할 때도 동일하다. 누적합 C배열을 참조하면 0이 들어갈 위치는 인덱스 2이다. 다시 말하면 0보다 작거나 같은 원소의 수가 2라는 이야기 이므로, A배열의 7번 인덱스 위치에 있는 0은, 정렬된 배열을 저장할 B 배열의 2번 인덱스에 저장되고, 누적합 C배열의 0번 인덱스의 값을 1로 1감소시킨다.

• 위의 방법으로 전체 원소의 들어갈 자리를 계산하면, (f)단계의 결과를 얻을 수 있다.

pseudo code

• 1, 2 - counter C배열을 0으로 초기화

• 3, 4 - 각각의 데이터들마다 카운팅을 한다.

• 6, 7 - 누적합을 구하는 부분이다. 카운터 배열 C를 참조하여 누적 합을 구한다.

• 9, 10, 11 - A[j]에 들어갈 값을 누적합이 저장된 C의 인덱스를 참조하여 B 배열에 저장한다.

• 다음으로, 누적합 C배열의 값을 1감소시킨다.

Counting-Sort(A, B, k)
1  for i <- 0 to k
2    do C[i] <- 0
3  for j <- 1 to length[A]
4    do C[A[j]] <- C[A[j]] + 1
5  => C[i] now contains the number of elements equal to i.
6  for i <- 1 to k
7    do C[i] <- C[i] + C[i-1]
8  => C[i] now contains the number of elements less than or equal to i.
9  for j <- length[A] downto 1
10   do B[C[A[j]]] <- A[j]
11      C[A[j]] <- C[A[j]] - 1

시간복잡도

• Θ(n+k), 또는 Θ(n) if k=O(n).

  • 일반적으로 n>k일 경우이다. k가 크지 않을경우 사용하는 방법이다. k가 n을 넘지 않는다고 가정하면 알고리즘의 시간복잡도는 Θ(n)이 된다.

• k가 클 경우 비 실용적이다.

• stable 정렬 알고리즘

  • "입력에 동일한 값이 있을때 입력에 먼저 나오는 값이 출력에서도 먼저 나온다."라는 성질을 만족하는 알고리즘.

  • Counting 정렬은 stable하다.