11.9 계수 정렬¶

계수 정렬(counting sort)은 원소의 개수를 세어 정렬하며, 주로 정수 배열에 사용한다.

11.9.1 간단한 구현¶

먼저 간단한 예를 보자. 길이가 \(n\)인 배열 nums의 모든 원소가 '음이 아닌 정수'라고 하자. 계수 정렬의 전체 과정은 아래 그림(11-16)과 같다.

배열을 순회하여 가장 큰 수 \(m\)을 찾고, 길이가 \(m + 1\)인 보조 배열 counter를 만든다.
counter를 이용하여 nums에서 각 수가 나타나는 횟수를 센다. counter[num]은 수 num의 등장 횟수다. 세는 방법은 간단하다. nums를 순회하면서 현재 수를 num이라고 할 때 counter[num]을 \(1\)씩 늘리면 된다.
counter의 인덱스는 본래 순서대로 배열되어 있으므로, 모든 수가 이미 정렬된 셈이다. 이어서 counter를 순회하며 각 수의 등장 횟수만큼 작은 수부터 큰 수 순서로 nums에 채우면 된다.

계수 정렬 과정

그림 11-16 계수 정렬 과정

코드는 다음과 같다.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

counting_sort.py

def counting_sort_naive(nums: list[int]):
    """계수 정렬"""
    # 간단한 구현이며, 객체 정렬에는 사용할 수 없다
    # 1. 배열의 최댓값 m을 구한다
    m = max(nums)
    # 2. 각 숫자의 등장 횟수를 센다
    # counter[num]은 num의 등장 횟수를 나타낸다
    counter = [0] * (m + 1)
    for num in nums:
        counter[num] += 1
    # 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    i = 0
    for num in range(m + 1):
        for _ in range(counter[num]):
            nums[i] = num
            i += 1

counting_sort.cpp

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
void countingSortNaive(vector<int> &nums) {
    // 1. 배열의 최댓값 m을 구한다
    int m = 0;
    for (int num : nums) {
        m = max(m, num);
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    vector<int> counter(m + 1, 0);
    for (int num : nums) {
        counter[num]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

counting_sort.java

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
void countingSortNaive(int[] nums) {
    // 1. 배열의 최댓값 m을 구한다
    int m = 0;
    for (int num : nums) {
        m = Math.max(m, num);
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    int[] counter = new int[m + 1];
    for (int num : nums) {
        counter[num]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

counting_sort.cs

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
void CountingSortNaive(int[] nums) {
    // 1. 배열의 최댓값 m을 구한다
    int m = 0;
    foreach (int num in nums) {
        m = Math.Max(m, num);
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    int[] counter = new int[m + 1];
    foreach (int num in nums) {
        counter[num]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

counting_sort.go

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
func countingSortNaive(nums []int) {
    // 1. 배열의 최댓값 m을 구한다
    m := 0
    for _, num := range nums {
        if num > m {
            m = num
        }
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    counter := make([]int, m+1)
    for _, num := range nums {
        counter[num]++
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    for i, num := 0, 0; num < m+1; num++ {
        for j := 0; j < counter[num]; j++ {
            nums[i] = num
            i++
        }
    }
}

counting_sort.swift

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
func countingSortNaive(nums: inout [Int]) {
    // 1. 배열의 최댓값 m을 구한다
    let m = nums.max()!
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    var counter = Array(repeating: 0, count: m + 1)
    for num in nums {
        counter[num] += 1
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    var i = 0
    for num in 0 ..< m + 1 {
        for _ in 0 ..< counter[num] {
            nums[i] = num
            i += 1
        }
    }
}

counting_sort.js

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
function countingSortNaive(nums) {
    // 1. 배열의 최댓값 m을 구한다
    let m = Math.max(...nums);
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    const counter = new Array(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

counting_sort.ts

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
function countingSortNaive(nums: number[]): void {
    // 1. 배열의 최댓값 m을 구한다
    let m: number = Math.max(...nums);
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    const counter: number[] = new Array<number>(m + 1).fill(0);
    for (const num of nums) {
        counter[num]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    let i = 0;
    for (let num = 0; num < m + 1; num++) {
        for (let j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
}

counting_sort.dart

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
void countingSortNaive(List<int> nums) {
  // 1. 배열의 최댓값 m을 구한다
  int m = 0;
  for (int _num in nums) {
    m = max(m, _num);
  }
  // 2. 각 숫자의 등장 횟수를 센다
  // counter[_num]은 _num의 등장 횟수를 나타낸다
  List<int> counter = List.filled(m + 1, 0);
  for (int _num in nums) {
    counter[_num]++;
  }
  // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
  int i = 0;
  for (int _num = 0; _num < m + 1; _num++) {
    for (int j = 0; j < counter[_num]; j++, i++) {
      nums[i] = _num;
    }
  }
}

counting_sort.rs

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
fn counting_sort_naive(nums: &mut [i32]) {
    // 1. 배열의 최댓값 m을 구한다
    let m = *nums.iter().max().unwrap();
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    let mut counter = vec![0; m as usize + 1];
    for &num in nums.iter() {
        counter[num as usize] += 1;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    let mut i = 0;
    for num in 0..m + 1 {
        for _ in 0..counter[num as usize] {
            nums[i] = num;
            i += 1;
        }
    }
}

counting_sort.c

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
void countingSortNaive(int nums[], int size) {
    // 1. 배열의 최댓값 m을 구한다
    int m = 0;
    for (int i = 0; i < size; i++) {
        if (nums[i] > m) {
            m = nums[i];
        }
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    int *counter = calloc(m + 1, sizeof(int));
    for (int i = 0; i < size; i++) {
        counter[nums[i]]++;
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    int i = 0;
    for (int num = 0; num < m + 1; num++) {
        for (int j = 0; j < counter[num]; j++, i++) {
            nums[i] = num;
        }
    }
    // 4. 메모리를 해제한다
    free(counter);
}

counting_sort.kt

/* 계수 정렬 */
// 간단한 구현이며, 객체 정렬에는 사용할 수 없다
fun countingSortNaive(nums: IntArray) {
    // 1. 배열의 최댓값 m을 구한다
    var m = 0
    for (num in nums) {
        m = max(m, num)
    }
    // 2. 각 숫자의 등장 횟수를 센다
    // counter[num]은 num의 등장 횟수를 나타낸다
    val counter = IntArray(m + 1)
    for (num in nums) {
        counter[num]++
    }
    // 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
    var i = 0
    for (num in 0..<m + 1) {
        var j = 0
        while (j < counter[num]) {
            nums[i] = num
            j++
            i++
        }
    }
}

counting_sort.rb

### 계수 정렬 ###
def counting_sort_naive(nums)
  # 간단한 구현이며, 객체 정렬에는 사용할 수 없다
  # 1. 배열의 최댓값 m을 구한다
  m = 0
  nums.each { |num| m = [m, num].max }
  # 2. 각 숫자의 등장 횟수를 센다
  # counter[num]은 num의 등장 횟수를 나타낸다
  counter = Array.new(m + 1, 0)
  nums.each { |num| counter[num] += 1 }
  # 3. counter를 순회하며 각 원소를 원래 배열 nums에 채운다
  i = 0
  for num in 0...(m + 1)
    (0...counter[num]).each do
      nums[i] = num
      i += 1
    end
  end
end

코드 시각화

전체 화면 >

계수 정렬과 버킷 정렬의 관계

버킷 정렬의 관점에서는 계수 배열 counter의 각 인덱스를 하나의 버킷으로, 개수를 세는 과정을 원소를 해당 버킷에 분배하는 과정으로 볼 수 있다. 본질적으로 계수 정렬은 정수 데이터에 적용되는 버킷 정렬의 특수한 경우다.

11.9.2 완전한 구현¶

주의 깊게 읽었다면 입력 데이터가 객체일 때 위의 3. 단계가 작동하지 않는다는 것을 알아차렸을 것이다. 입력이 상품 객체이고 상품 가격(클래스의 멤버 변수)에 따라 정렬하려 한다고 하자. 위 알고리즘으로는 가격의 정렬 결과만 얻을 수 있다.

그렇다면 원래 데이터의 정렬 결과는 어떻게 얻을까? 먼저 counter의 '접두 합'을 계산한다. 이름 그대로 인덱스 i의 접두 합 prefix[i]는 배열의 앞 i 개 원소를 더한 값이다.

\[ \text{prefix}[i] = \sum_{j=0}^i \text{counter[j]} \]

접두 합은 명확한 의미를 가진다. prefix[num] - 1은 결과 배열 res에서 원소 num이 마지막으로 나타나는 인덱스다. 이는 각 원소가 결과 배열의 어디에 놓여야 하는지 알려 주는 핵심 정보다. 이어서 원래 배열 nums의 각 원소 num을 역순으로 순회하며 매번 다음 두 단계를 수행한다.

배열 res의 인덱스 prefix[num] - 1에 num을 넣는다.
접두 합 prefix[num]을 \(1\) 줄여 다음에 num을 넣을 인덱스를 얻는다.

순회를 마치면 배열 res에 정렬된 결과가 들어 있다. 마지막으로 res를 원래 배열 nums에 덮어쓰면 된다. 아래 그림(11-17)은 계수 정렬의 전체 과정을 보여 준다.

그림 11-17 계수 정렬 단계

계수 정렬의 구현 코드는 다음과 같다.