계수 정렬 (Counting sort)

계수 정렬

계수 정렬은 수를 정렬하는 알고리즘이다. 수의 개수를 세서 배열에 저장한다. 예를 들어 [3, 2, 5, 7, 8, 1, 2]라는 데이터가 차례대로 들어왔다고 하자. 입력된 수들의 개수를 세서 이를 그대로 배열에 저장하면 된다.

위의 배열은 수의 개수를 나타내는 카운트 배열이다. 위 배열에서 카운트가 0인 인덱스를 제외하면 압축된 배열을 얻을 수 있다. 압축하면 다음과 같은 배열이다.

조건

계수 정렬을 효율적으로 사용할 수 있는 조건이 있다.

먼저, 데이터의 범위가 0과 양의 정수여야 한다. 입력된 값이 음수라면 배열 인덱싱을 하지 못한다. 만약 입력되는 값의 범위가 -4000 ~ +4000으로 정해져있다면 input + 4000값을 인덱싱하는 것으로 임의로 계수 정렬을 사용할 수 있다.

범위가 일정해야한다. 입력되는 값의 간극이 1, 5823처럼 많이 벌어지면 이 값을 인덱싱하기 위한 배열의 메모리가 많이 소모된다. 그렇기 때문에 시험 성적같이 데이터의 범위가 정해져있는 것이 계수 정렬을 사용하는데 효율적이다.

시간복잡도

시간복잡도는 O(n)이다.

• 카운트 배열에 저장하기 위해서 n 번의 연산
• 정렬된 배열을 만들기 위해 (n + k) 번의 연산
• k는 카운트 배열의 크기이다. 입력되는 값의 범위가 0 ~ 999라면 k는 1000이 된다.

예제 코드

#include <cmath>

using namespace std;

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

    int count[100] = {0};
    int input;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        count[input]++;
    }
    
    int j = 0;
    int *resultArr = (int *)malloc(sizeof(int) * N);
    for (int i = 0; i < N; i++)
    {
        while (true)
        {
            if (count[j] > 0)
                break;
            else
                j++;
        }
        resultArr[i] = j - 4000;
        count[j]--;
    }
    
    return 0;
}