계수 정렬

개요 :

계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘이 아닌 카운팅을 기반으로 하는 정렬 알고리즘입니다. 주로 정수 값이나 범위가 제한된 값들을 정렬할 때 매우 효율적입니다. 값의 범위가 크지 않거나 제한적인 경우에 매우 빠르게 동작하며, 시간 복잡도가 O(n + k)로, n은 입력 배열의 크기, k는 배열 값의 범위입니다.

원리 :

계수 정렬의 핵심 아이디어는 각 값의 등장 횟수를 세고, 그 정보를 바탕으로 정렬된 배열을 만들어내는 것입니다. 각 값이 배열에서 몇 번 나타나는지를 기록하는 카운팅 배열을 이용하여 최종적으로 정렬을 수행합니다.

사용 조건 :

1. 값의 범위가 제한적인 경우
2. 배열의 크기 N에 비해 값의 범위 K가 상대적으로 작은 경우
3. 수의 범위가 작고, 동일한 수가 많이 반복될 때
4. 출력 순서가 중요한 경우

#include <iostream>

using namespace std;

int main() 
{
    int N;
    cin >> N;

    int* count = new int[10001]();

    for (int i = 0; i < N; ++i) 
    {
        int num;
        cin >> num;
        count[num]++;
    }

    for (int i = 1; i <= 10000; ++i) 
        while (count[i]--) 
            cout << i << "\n";

    delete[] count;

    return 0;
}

 

문제 풀어보기 : BeakJoon