Counting Sort

Q: 계수 정렬의 시간 복잡도는 무엇인가요?

계수 정렬은 `O(n + k)`이며, 여기서 `n`은 원소 수, `k`는 가능한 값의 범위입니다. `k = O(n)`일 때 이는 선형 시간입니다. 추가로 `O(n + k)` 공간을 사용합니다.

Q: 계수 정렬은 안정적인가요?

그럴 수 있습니다. 안정 버전은 계수의 접두사 합을 만들고 원소를 오른쪽에서 왼쪽으로 배치하여 같은 키의 상대적 순서를 보존합니다. 여기 보인 단순한 "값으로 다시 쓰기" 버전은 올바른 정렬을 만들지만 주로 단순 정수에 사용됩니다.

Q: 계수 정렬은 언제 사용해야 하나요?

정수(또는 정수로 매핑할 수 있는 키)를 작고 알려진 범위에서 정렬할 때 사용하세요. 값의 범위 `k`가 원소 수보다 훨씬 크면 계수 배열이 메모리를 낭비하므로 비교 정렬이 더 낫습니다.

Q: 계수 정렬과 기수 정렬(radix sort)의 차이는 무엇인가요?

계수 정렬은 한 번의 패스로 값 전체를 기준으로 정렬하며 값의 범위만큼 큰 계수 배열이 필요합니다. 기수 정렬은 자릿수별로 정렬하고 보통 각 자릿수에 대해 안정적인 계수 정렬을 호출하여 패스당 범위를 작게 유지합니다(예: 10진 자릿수의 경우 `10`). 기수 정렬은 단일 계수 정렬로는 비현실적이 되는 큰 값의 범위를 처리합니다.

Q: 왜 계수 정렬이 항상 퀵정렬(quicksort)보다 빠르지는 않나요?

계수 정렬은 `O(n + k)`이므로 값의 범위 `k`가 `n`과 비슷할 때만 유리합니다. `k`가 거대하면 - 예를 들어 `0`부터 `1,000,000,000` 범위의 값 100개를 정렬하면 - `O(k)` 계수 배열이 지배적이 되어 메모리를 낭비하지만, 퀵정렬 같은 `O(n log n)` 비교 정렬은 빠르고 공간 효율적으로 유지됩니다.

Q: 계수 정렬은 음수를 처리할 수 있나요?

네, 작은 오프셋으로 가능합니다. 계수 배열을 값으로 직접 인덱싱하는 대신 `value - min`으로 인덱싱하여 가장 작은 값이 인덱스 `0`에 매핑되도록 합니다. 계수 배열의 크기는 `max - min + 1`이 됩니다. 이 오프셋을 잊는 것은 음수 입력에서 충돌을 일으키는 흔한 버그입니다.

마지막 업데이트 2026년 7월 1일

계수 정렬은 알려진 제한된 범위의 정수를 위한 비교 없는 정렬입니다. 각 값이 몇 번 나타나는지 세고, 그 계수를 사용해 각 값을 바로 정렬된 위치에 씁니다. 비교가 필요 없습니다. 위의 재생 버튼을 눌러 값이 집계된 뒤 순서대로 배치되는 과정을 확인하세요.

계수 정렬은 O(n + k) 시간에 동작하며, 여기서 k는 입력 값의 범위입니다. k가 n보다 그리 크지 않을 때 매우 빠르며 O(n log n) 비교 정렬을 능가할 수 있지만, 값의 범위가 거대하면 O(k) 계수 배열 때문에 비현실적이 됩니다.

시간 및 공간 복잡도

경우	복잡도	비고
시간	O(n + k)	n개 원소, k = 값의 범위
공간	O(n + k)	계수 배열 + 출력 배열
안정성	예	접두사 합을 사용해 오른쪽에서 왼쪽으로 배치할 때
비교?	아니오	비교가 아니라 계수로 정렬함
가장 적합	작은 정수 범위	k가 n에 가까운 경우

단계별 과정

단계	무슨 일이 일어나는가
1	계수 배열의 크기를 정하기 위해 최댓값을 찾는다.
2	각 값이 몇 번 나타나는지 센다.
3	(선택) 안정성을 위해 계수를 접두사 합으로 변환한다.
4	각 값을 나타난 횟수만큼 출력에 쓴다.
5	출력 배열이 이제 완전히 정렬되었다.

예제 풀이

[1, 4, 1, 2, 4] 정렬하기 (값이 0부터 4까지이므로 계수 배열은 5개의 칸을 가짐):

패스	상태	동작
입력 순회	count = `[0, 2, 1, 0, 2]`	출현 횟수 집계: `1`은 두 번, `2`는 한 번, `4`는 두 번 나타난다.
접두사 합	count = `[0, 2, 3, 3, 5]`	각 칸은 이제 자신의 인덱스 `<=`인 값이 몇 개인지 보관하며, 최종 위치를 제공한다.
`4` 배치	output = `[_, _, _, _, 4]`	오른쪽에서 왼쪽으로 읽음: `count[4] = 5`이므로 `4`는 인덱스 `4`로 간다; `4`로 감소시킨다.
`2` 배치	output = `[_, _, 2, _, 4]`	`count[2] = 3`이므로 `2`는 인덱스 `2`로 간다; `2`로 감소시킨다.
`1` 배치	output = `[_, 1, 2, _, 4]`	`count[1] = 2`이므로 `1`은 인덱스 `1`로 간다; `1`로 감소시킨다.
`4` 배치	output = `[_, 1, 2, 4, 4]`	`count[4] = 4`이므로 이 `4`는 인덱스 `3`으로 간다; `3`으로 감소시킨다.
`1` 배치	output = `[1, 1, 2, 4, 4]`	`count[1] = 1`이므로 이 `1`은 인덱스 `0`으로 간다. 배열이 정렬되었다.

계수 정렬을 사용할 때

사용해야 할 때	피해야 할 때
정수(또는 정수로 매핑할 수 있는 키)를 작고 알려진 범위에서 정렬할 때.	값의 범위 `k`가 원소 수 `n`보다 훨씬 클 때.
선형 `O(n + k)` 시간이 필요하고 추가 배열을 감당할 수 있을 때.	메모리가 빠듯할 때 - 계수 배열은 `n`과 무관하게 `O(k)` 비용이 든다.
서브루틴으로 안정 정렬이 필요할 때(예: 기수 정렬 내부).	키가 부동소수점, 문자열, 또는 정수로 매핑되지 않는 임의의 객체일 때.
최댓값이 유계이고 미리 저렴하게 계산할 수 있을 때.	범위가 알려지지 않았거나 무한하여 계수 배열의 크기를 정할 수 없을 때.

Counting Sort 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Counting Sort 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Counting Sort 코드Python
1def counting_sort(a):2    # Works for non-negative integers with a small max value3    counts = [0] * (max(a) + 1)4    for value in a:5        counts[value] += 16    # Prefix sums turn counts into final positions7    for i in range(1, len(counts)):8        counts[i] += counts[i - 1]9    out = [0] * len(a)10    for value in reversed(a):  # reversed keeps equal values stable11        counts[value] -= 112        out[counts[value]] = value13    return out14
15
16nums = [4, 2, 2, 8, 3, 3, 1]17print("Before:", nums)18print("After: ", counting_sort(nums))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Counting Sort 코드JavaScript
1function countingSort(arr) {2    // Count occurrences of each value, then rebuild in order3    const max = Math.max(...arr);4    const count = new Array(max + 1).fill(0);5    for (const x of arr) count[x]++;6    const out = [];7    count.forEach((c, value) => {8        for (let k = 0; k < c; k++) out.push(value);9    });10    return out;11}12
13const data = [4, 2, 9, 2, 7, 4, 1, 4];14console.log("Before:", data);15console.log("Sorted:", countingSort(data));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Counting Sort 코드Java
1import java.util.Arrays;2
3public class Main {4    static int[] countingSort(int[] arr) {5        int max = 0;6        for (int v : arr) max = Math.max(max, v);7        int[] count = new int[max + 1];8        for (int v : arr) count[v]++;9        // Prefix sums turn counts into final positions10        for (int i = 1; i <= max; i++) count[i] += count[i - 1];11        int[] out = new int[arr.length];12        // Walk backwards so equal values keep their order (stable)13        for (int i = arr.length - 1; i >= 0; i--) {14            out[--count[arr[i]]] = arr[i];15        }16        return out;17    }18
19    public static void main(String[] args) {20        int[] arr = {4, 2, 2, 8, 3, 3, 1};21        System.out.println("Before: " + Arrays.toString(arr));22        int[] sorted = countingSort(arr);23        System.out.println("After:  " + Arrays.toString(sorted));24    }25}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Counting Sort 코드C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6    for (int x : a) std::cout << x << " ";7    std::cout << "\n";8}9
10void countingSort(std::vector<int>& a) {11    if (a.empty()) return;12    int maxVal = *std::max_element(a.begin(), a.end());13    // count[v] = how many times v appears14    std::vector<int> count(maxVal + 1, 0);15    for (int x : a) ++count[x];16    // Rebuild the array from the counts17    size_t idx = 0;18    for (int v = 0; v <= maxVal; ++v) {19        while (count[v]-- > 0) a[idx++] = v;20    }21}22
23int main() {24    std::vector<int> data = {4, 2, 2, 8, 3, 3, 1, 7};25    std::cout << "Before: ";26    printVec(data);27    countingSort(data);28    std::cout << "After:  ";29    printVec(data);30    return 0;31}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Counting Sort 코드C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5    for (int i = 0; i < n; i++) printf("%d ", a[i]);6    printf("\n");7}8
9void countingSort(int a[], int n) {10    int maxVal = a[0];11    for (int i = 1; i < n; i++) {12        if (a[i] > maxVal) maxVal = a[i];13    }14    // count[v] = how many times v appears15    int* count = calloc(maxVal + 1, sizeof(int));16    for (int i = 0; i < n; i++) count[a[i]]++;17    // Rebuild the array from the counts18    int idx = 0;19    for (int v = 0; v <= maxVal; v++) {20        while (count[v]-- > 0) a[idx++] = v;21    }22    free(count);23}24
25int main(void) {26    int data[] = {4, 2, 2, 8, 3, 3, 1, 7};27    int n = sizeof(data) / sizeof(data[0]);28    printf("Before: ");29    printArr(data, n);30    countingSort(data, n);31    printf("After:  ");32    printArr(data, n);33    return 0;34}
이 코드를 C 플레이그라운드에서 실행하기

계수 정렬 FAQ

계수 정렬의 시간 복잡도는 무엇인가요?

계수 정렬은 O(n + k)이며, 여기서 n은 원소 수, k는 가능한 값의 범위입니다. k = O(n)일 때 이는 선형 시간입니다. 추가로 O(n + k) 공간을 사용합니다.

계수 정렬은 안정적인가요?

그럴 수 있습니다. 안정 버전은 계수의 접두사 합을 만들고 원소를 오른쪽에서 왼쪽으로 배치하여 같은 키의 상대적 순서를 보존합니다. 여기 보인 단순한 "값으로 다시 쓰기" 버전은 올바른 정렬을 만들지만 주로 단순 정수에 사용됩니다.

계수 정렬은 언제 사용해야 하나요?

정수(또는 정수로 매핑할 수 있는 키)를 작고 알려진 범위에서 정렬할 때 사용하세요. 값의 범위 k가 원소 수보다 훨씬 크면 계수 배열이 메모리를 낭비하므로 비교 정렬이 더 낫습니다.

계수 정렬과 기수 정렬(radix sort)의 차이는 무엇인가요?

계수 정렬은 한 번의 패스로 값 전체를 기준으로 정렬하며 값의 범위만큼 큰 계수 배열이 필요합니다. 기수 정렬은 자릿수별로 정렬하고 보통 각 자릿수에 대해 안정적인 계수 정렬을 호출하여 패스당 범위를 작게 유지합니다(예: 10진 자릿수의 경우 10). 기수 정렬은 단일 계수 정렬로는 비현실적이 되는 큰 값의 범위를 처리합니다.

왜 계수 정렬이 항상 퀵정렬(quicksort)보다 빠르지는 않나요?

계수 정렬은 O(n + k)이므로 값의 범위 k가 n과 비슷할 때만 유리합니다. k가 거대하면 - 예를 들어 0부터 1,000,000,000 범위의 값 100개를 정렬하면 - O(k) 계수 배열이 지배적이 되어 메모리를 낭비하지만, 퀵정렬 같은 O(n log n) 비교 정렬은 빠르고 공간 효율적으로 유지됩니다.

계수 정렬은 음수를 처리할 수 있나요?

네, 작은 오프셋으로 가능합니다. 계수 배열을 값으로 직접 인덱싱하는 대신 value - min으로 인덱싱하여 가장 작은 값이 인덱스 0에 매핑되도록 합니다. 계수 배열의 크기는 max - min + 1이 됩니다. 이 오프셋을 잊는 것은 음수 입력에서 충돌을 일으키는 흔한 버그입니다.