From: CLRS

계수 정렬(counting sort)은 \(n\) 개의 입력 원소 각각이 \(0\)부터 \(k\) 사이에 있는 정수라고 가정한다. \(k = O(n)\)일 때 계수 정렬은 \(\Theta(n)\) 시간에 수행된다.

계수 정렬은 각 입력 원소 \(x\)에 대해 \(x\)보다 작은 원소의 개수를 센다. 이 정보는 출력 배열에서 원소 \(x\)의 위치를 정하는 데 직접 사용된다. 예를 들어, \(x\)보다 작은 원소가 17개라면 \(x\)는 출력 배열에서 18번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다.

계수 정렬의 코드에서 입력이 배열 \(A[1..n]\) 이라고 가정하므로 \(A.length = n\) 이다. 또한 두 개의 다른 배열도 필요로 하는데 정렬된 출력을 저장할 배열 \(B[1..n]\)과 임시 작업 공간을 제공할 배열 \(C[0..K]\) 다.1

알고리즘과 성능 특성

// C[0..k]를 새로운 배열로 한다.
for i = 0 to k
  C[i] = 0
for j = 1 to A.length
  C[A[j]] = C[A[j]] + 1
// C[i]는 이제 i와 같은 원소의 개수를 나타낸다.
for i = 1 to k
  C[i] = C[i] + C[i-1]
// C[i]는 이제 값이 i 보다 작거나 같은 원소의 개수를 나타낸다.
for j = A.length downto 1
  B[C[A[j]]] = A[j]
  C[A[j]] = C[A[j]] - 1

계수 정렬은 시간이 얼마나 걸릴까? 2-3 행의 for 루프는 \(\Theta(k)\) 시간, 4-5 행의 for 루프는 \(\Theta(n)\) 시간, 7-8 행의 루프는 \(\Theta(k)\) 시간, 10-12 행의 for 루프는 \(\Theta(n)\) 시간이 걸린다. 따라서 총 시간은 \(\Theta(k+n)\) 이다. 실제 상황에서는 보통 \(k = O(n)\) 일 때 계수 정렬을 사용하고, 이 경우 수행시간은 \(\Theta(n)\) 이다.

계수 정렬은 비교 정렬이 아니므로 8.1 절에서 증명한 하한 \(\Omega(n \lg n)\)의 제약을 받지 않는다. 실제로 코드 어디에서도 입력 원소끼리 비교하는 부분이 없다. 대신 계수 정렬은 원소의 실제 값을 배열의 인덱스로 사용한다. \(\Omega(n \lg n)\)이라는 정렬의 하한은 비교 정렬이 아니면 적용되지 않는다.

계수 정렬의 중요한 특징은 안정성(stable)을 가진다는 점이다. 이는 출력 배열에서 값이 같은 숫자가 입력 배열에 있던 것과 같은 순서로 나타나는 것을 뜻한다. 즉, 두 숫자가 같을 때는 입력 배열에서 먼저 나타나는 것이 출력 배열에서도 먼저 나타난다. 보통 안정성이라는 특성이 중요할 때는 정렬되는 원소에 부속 데이터가 붙어 다닐 때뿐이다. 계수 정렬의 안정성은 다른 이유로도 중요한데, 계수 정렬이 종종 기수 정렬의 서브 루틴으로 쓰이기 때문이다. 다음 절에서 기수 정렬이 정확하게 동작하기 위해 계수 정렬의 안정성이 필수임을 보게 될 것이다. 1

  • 최대값과 최소값을 알아야 쓸 수 있다.
  • [[/algorithm/sort-stability]]{안정 정렬}에 해당한다.
  • 원소끼리 비교하는 정렬이 아니므로 비교 정렬의 하한인 \(\Omega( n \lg n )\) 제약이 없다.
  • 시간 복잡도는 \(\Theta(k+n)\).
    • 배열 C를 생성하는데 \(\Theta(k)\)
    • 배열 C에 카운팅 값을 입력하는데 \(\Theta(n)\)
    • 배열 C에 누적값을 업데이트하는데 \(\Theta(k)\)
    • 정렬 결과 배열 B를 채우는데 \(\Theta(n)\)

계수 정렬의 예

다음 배열 A를 계수 정렬 알고리즘을 사용해 정렬한다고 하자.

A [ 2 5 3 0 2 3 0 3 ]

최대값, 최소값 파악

계수 정렬을 사용하려면 정렬 대상 배열의 최소값과 최대값을 알아야 한다.

배열 A에 포함된 값들의 최소값이 0 이고, 최대값이 5이므로 길이가 6인 counting 배열 C를 만든다.

A [ 2 5 3 0 2 3 0 3 ]  C [ 0 0 0 0 0 0 ]
                           0 1 2 3 4 5 (index)

각 원소의 수 카운트

이제 A 배열을 한 번 돌면서 각 값의 빈도를 C 배열에 기록해 둔다.

for (int i = 0; i < A.length; i++) {
    C[A[i]]++;
}

다음은 루프가 완료되어 배열 C가 완성된 모습니다.

A [ 2 5 3 0 2 3 0 3 ]  C [ 2 0 2 3 0 1 ]
                           0 1 2 3 4 5 (index)

배열 C의 값을 살펴보자. 배열 A에 0이 2개 있고, 2가 2개 있고, 3이 3개 있고, 5가 1개 있다는 사실이 잘 기록되었다.

카운트 배열을 누적값으로 변환

이제 배열 C를 순회하며 누적값을 입력한다. 이렇게 하면 배열 C의 값들은 i보다 작거나 같은 수의 개수가 된다.

for (int i = 1; i < C.length; i++) {
    C[i] += C[i-1];
}

A [ 2 5 3 0 2 3 0 3 ]  C [ 2 2 4 7 7 8 ]
                           0 1 2 3 4 5 (index)

이제 배열 C는 다음을 표현한다.

는 0 보다 작거나 같은 수는 2개, 1보다 작거나 같은 수가 2개, 2보다 작거나 같은 수가 4개, 3보다 작거나 같은 수가 7개, 4보다 작거나 같은 수가 7개, 5보다 작거나 같은 수가 8개 있다.

정렬 결과 배열 생성

이제 정렬된 결과를 집어넣을 배열 B를 만든다. 배열 B는 배열 A와 사이즈가 같아야 한다. 단, 편의상 배열 B의 인덱스는 1부터 시작한다고 하자.

A [ 2 5 3 0 2 3 0 3 ]  C [ 2 2 4 7 7 8 ]
                           0 1 2 3 4 5 (index)
B [ _ _ _ _ _ _ _ _ ]
    1 2 3 4 5 6 7 8 (index)

이제 A 배열을 뒤에서부터 돌면서 숫자를 배치한다. A 배열의 마지막 원소는 3 이다.

이제 C[3]값이 무엇인지를 찾아본다. 그 값은 7 이다.

                  v              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 2 2 4 7 7 8 ]
                v          0 1 2 3 4 5 (index)
B [ _ _ _ _ _ _ _ _ ]
    1 2 3 4 5 6 7 8 (index)

그러므로 B[7] 에 3을 넣어주고, 3 한 개의 위치를 결정했으므로, C[3]의 값에서 1을 빼 준다.

                  v              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 2 2 4 6 7 8 ]
                v          0 1 2 3 4 5 (index)
B [ _ _ _ _ _ _ 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 0 이다. C[0]의 값을 찾아보니 2가 나온다. 그렇다면 0은 B[0]에 들어가면 된다.

                v .        v
A [ 2 5 3 0 2 3 0 3 ]  C [ 2 2 4 6 7 8 ]
      v                    0 1 2 3 4 5 (index)
B [ _ _ _ _ _ _ 3 _ ]
    1 2 3 4 5 6 7 8 (index)

다음과 같이 B[2]에 0을 넣어준다. 그리고 C[0]에서 1을 빼 준다.

                v .        v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 4 6 7 8 ]
      v                    0 1 2 3 4 5 (index)
B [ _ 0 _ _ _ _ 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 3 이다. C[3]의 값을 찾아보니 6이다. 그렇다면 3은 B[6]에 들어가면 된다.

              v . .              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 4 6 7 8 ]
              v            0 1 2 3 4 5 (index)
B [ _ 0 _ _ _ _ 3 _ ]
    1 2 3 4 5 6 7 8 (index)

B[6]에 3을 넣어주고, C[3]에서 1을 빼 준다.

              v . .              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 4 5 7 8 ]
              v            0 1 2 3 4 5 (index)
B [ _ 0 _ _ _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 2 이다. C[2]의 값을 찾아보니 4이다. 그렇다면 2은 B[4]에 들어가면 된다.

            v . . .            v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 4 5 7 8 ]
          v                0 1 2 3 4 5 (index)
B [ _ 0 _ _ _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

B[4]에 2를 넣어주고, C[2]에서 1을 빼 준다.

            v . . .            v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 3 5 7 8 ]
          v                0 1 2 3 4 5 (index)
B [ _ 0 _ 2 _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 0 이다. C[0]의 값을 찾아보니 1이다. 그렇다면 0은 B[1]에 들어가면 된다.

          v . . . .        v
A [ 2 5 3 0 2 3 0 3 ]  C [ 1 2 3 5 7 8 ]
    v                      0 1 2 3 4 5 (index)
B [ _ 0 _ 2 _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

B[1]에 0를 넣어주고, C[0]에서 1을 빼 준다.

          v . . . .        v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 5 7 8 ]
    v                      0 1 2 3 4 5 (index)
B [ 0 0 _ 2 _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 3 이다. C[3]의 값을 찾아보니 5이다. 그렇다면 3은 B[5]에 들어가면 된다.

        v . . . . .              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 5 7 8 ]
            v              0 1 2 3 4 5 (index)
B [ 0 0 _ 2 _ 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

B[5]에 3를 넣어주고, C[3]에서 1을 빼 준다.

        v . . . . .              v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 4 7 8 ]
            v              0 1 2 3 4 5 (index)
B [ 0 0 _ 2 3 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 5 이다. C[5]의 값이 8이므로, 5는 B[8]에 들어가면 된다.

      v . . . . . .                  v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 4 7 8 ]
                  v        0 1 2 3 4 5 (index)
B [ 0 0 _ 2 3 3 3 _ ]
    1 2 3 4 5 6 7 8 (index)

B[8]에 5를 넣어주고, C[5]에서 1을 빼 준다.

      v . . . . . .                  v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 4 7 7 ]
                  v        0 1 2 3 4 5 (index)
B [ 0 0 _ 2 3 3 3 5 ]
    1 2 3 4 5 6 7 8 (index)

A 배열의 다음 값은 2 이다. C[2]의 값이 3이므로, 2는 B[3]에 들어가면 된다.

    v . . . . . . .            v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 3 4 7 7 ]
        v                  0 1 2 3 4 5 (index)
B [ 0 0 _ 2 3 3 3 5 ]
    1 2 3 4 5 6 7 8 (index)

B[3]에 2를 넣어주고, C[2]에서 1을 빼 준다.

    v . . . . . . .            v
A [ 2 5 3 0 2 3 0 3 ]  C [ 0 2 2 4 7 7 ]
        v                  0 1 2 3 4 5 (index)
B [ 0 0 2 2 3 3 3 5 ]
    1 2 3 4 5 6 7 8 (index)

정렬 결과

배열 B가 배열 A를 정렬한 결과이다.

A [ 2 5 3 0 2 3 0 3 ]
B [ 0 0 2 2 3 3 3 5 ]

달력의 비유

작은 음식점의 장부를 책임진 회계사가 있다. 매일 밤, 음식점 문을 닫으면 지배인은 당일 판매 기록을 정리하고 날짜와 총 금액이 적힌 영수증을 끊는다. 이 영수증은 큰 상자에 던져둔다. 연말에 회계사는 상자 안의 영수증을 보고 빠진 게 있는지 점검한다. 짐작이 가겠지만, 상자 안의 영수증은 뒤죽박죽 섞여 있다.

회계사는 날짜순으로 영수증을 정돈한 다음, 정렬된 집합을 검토할 수 있다. 또 다른 방법으로 상자에서 영수증을 하나씩 꺼내면서, 빈 달력에 X 표시를 할 수도 있다. 상자 안의 영수증을 다 꺼내면 회계사는 달력에 표시가 없는 날짜가 있는지 검토하면 된다. 두 번째 방법에선 한 번도 두 영수증을 서로 비교하지 않았다. 음식점이 개업한 지 60년이 됐고 회계사가 그동안의 달력을 모두 갖고 있다면, (영수증이 5장 뿐이라면 효율적이지 않지만 20,000 장이 있다면) 이 방법이 효율적이다. 자료 집합에서 실제로 나타날 수 있는 원소의 밀도가 높을수록 이 접근법의 효율이 좋아진다. 2

함께 읽기

  • [[/algorithm/sort-stability]]{안정 정렬}

참고문헌

  • [CLRS] Introduction to Algorithms 3판 / 토머스 코멘, 찰스 레이서손, 로날드 리베스트, 클리포드 스타인 공저 / 문병로, 심규석, 이충세 공역 / 한빛아카데미 / 2014년 06월 30일
  • [NUT] 사전처럼 바로 찾아 쓰는 알고리즘 / 조지 T. 하인만, 게리 폴리케, 스탠리 셀코 공저 / 전경원 역 / 한빛미디어 / 초판 2쇄 2011년 10월 20일 / 원제: Algorithms In A Nutshell

주석

  1. [CLRS] 8.2장 ↩ ↩2

  2. [NUT] 4장. 계수 정렬 ↩