계수 정렬 (Counting sort)

주어진 수들을 정렬해야 하는 경우, 수들이 모두 양수이고, 최대값이 정해져 있다면.

카운팅 정렬 (계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다.

 

 

■ 계수 정렬?

 

계수 정렬 알고리즘은 비교를 하지 않는다.

배열의 인덱스를 사용하여 숫자의 개수를 카운팅, 순서대로 출력하는 것이다.

매우 간단하다.

 

계수 정렬의 시간복잡도는 O(n) 으로 실행 시간은 짧지만 사용하기 위해 조건이 있다.

 

먼저 주어진 숫자들이 자연수이고, 최대값이 너무 크지 않아야 한다.

배열의 인덱스를 사용 할 것이기 때문에 양수만 가능하고,

최대값이 너무 커져버리면 메모리에 부담이 커진다.

 

이러한 조건 때문에 다른 정렬 알고리즘만큼 많이 쓰이지는 않는다.

하지만 위 조건을 충족하는 경우 다른 정렬 알고리즘보다 효율적으로 정렬할 수 있다.

 

 

■ 정렬 과정

 

배열의 크기가 N 이고, 원소의 최대값이 6이라고 해보자.

먼저, count 배열을 만들고 N 번 반복하며 배열의 원소들을 count 배열의 인덱스 값으로 하여

count 배열의 값을 증가시킨다.

이렇게 하면 count 배열에 기존 배열의 원소가 각각 몇 개 씩 있는지 저장된다.

 

예를 들어 data = { 2, 6, 2, 6, 3, 4 } 배열이 있다면

count 배열은 

인덱스	0	1	2	3	4	5	6
값	0	0	2	1	1	0	2

와 같이 생성된다.

 

이렇게 만들어지면 count 배열의 값들이 몇 번째 정렬 위치인지 저장하기 위해

배열의 1번 인덱스 부터 이전 인덱스의 값을 더해준다.

그렇게 되면

인덱스	0	1	2	3	4	5	6
값	0	0	2	3	4	4	6

위와 같이 된다.

 

그런데, 여기서 의문점이 하나 생긴다. 배열에 5는 없었는데 이번 과정을 거치니 4로 카운트 되어있다.

하지만 우리는 count 배열을 참조하여 정렬 할 값을 가져올 때,

data 배열 원소의 값을 인덱스로 하여 참조 할 것이기 때문에 문제없다.

 

이제 정렬된 배열을 저장할 배열 ans 를 만든다.

그리고 data 배열의 원소를 count 배열의 인덱스로 하고

그 값으로 위치를 확인, ans 배열의 해당 위치에 인덱스 값을 넣는다.

 

아래를 통해 정렬 순서를 자세히 알아보자.

①  data 배열의 2를 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	2	3	4	4	6

count 배열의 2번 인덱스의 값은 2이다.

ans 배열의 두 번째 위치에 2를 넣자. (배열에서는 실제 위치는 값 - 1 이 된다.)

인덱스	0	1	2	3	4	5
값		2

이제 count 의 2번 인덱스의 값에서 1을 뺀다.

②  data 배열의 6을 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	1	3	4	4	6

count 배열의 6번 인덱스의 값은 6이다.

ans 배열의 여섯 번째 위치에 6을 넣자.

인덱스	0	1	2	3	4	5
값		2				6

이제 count 의 6번 인덱스의 값에서 1을 뺀다.

③ data 배열의 2를 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	1	3	4	4	5

count 배열의 2번 인덱스의 값은 1이다.

ans 배열의 첫 번째 위치에 2를 넣자.

인덱스	0	1	2	3	4	5
값	2	2				6

이제 count 의 2번 인덱스의 값에서 1을 뺀다.

④  data 배열의 6을 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	0	3	4	4	5

count 배열의 6번 인덱스의 값은 5이다.

ans 배열의 다섯 번째 위치에 6을 넣자.

인덱스	0	1	2	3	4	5
값	2	2			6	6

이제 count 의 6번 인덱스의 값에서 1을 뺀다.

⑤  data 배열의 3을 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	0	3	4	4	5

count 배열의3번 인덱스의 값은 3이다.

ans 배열의 세 번째 위치에 3을 넣자.

인덱스	0	1	2	3	4	5
값	2	2	3		6	6

이제 count 의 3번 인덱스의 값에서 1을 뺀다.

⑥  data 배열의 4를 인덱스로.

인덱스	0	1	2	3	4	5	6
값	0	0	0	2	4	4	5

count 배열의 4번 인덱스의 값은 4이다.

ans 배열의 네 번째 위치에 4를 넣자.

인덱스	0	1	2	3	4	5
값	2	2	3	4	6	6

이제 count 의 4번 인덱스의 값에서 1을 뺀다.

 

 

이렇게 여기까지가 Counting Sort, 계수 정렬의 순서이다.

 

 

위 순서에서 2를 정렬 할 때를 보자.

2가 두 개 있는데 배열의 두 번째 자리부터 채워지고, 그 다음 2가 그 앞에 채워지는 것을 볼 수 있다.

동일한 데이터에 대해서 순서가 바뀌는 것에 따라 Stable 방식과 Unstable 방식으로 나뉜다.

 

아래의 예시로 간단히 살펴보자.

{ 2, 6, 2, 6, 3, 4 } 배열이 있다면

Stable 방식 정렬은 

인덱스	0	1	2	3	4	5
값	2	2	3	4	6	6

위와 같이 같은 숫자의 순서가 바뀌지 않고 정렬이 된다.

 

Unstable 방식에서는 

인덱스	0	1	2	3	4	5
값	2	2	3	4	6	6

위와 같이 같은 숫자의 순서가 바뀌게 된다.

 

이는 data 배열의 앞, 뒤 어디에서부터 값을 확인하며 가져오냐에 따라 방식이 나뉘게 된다.

위의 순서를 보여주는 부분에서는 data 배열의 앞에서 부터 값을 확인하며 가져왔고,

Unstable 방식으로 정렬되었다.

 

Stable 방식으로 정렬하고 싶다면 맨 뒤부터 값을 확인하며 가져오자.

 

 

■ 코드로 구현 (C++)

#include <iostream>
#define MAX_DATA 10000000
using namespace std;

int cnt[10001] = { 0, }, ans[MAX_DATA], list[MAX_DATA];

void counting_sort(int data[], int n) {
    for (int i = 0; i < n; i++) cnt[data[i]]++;
    for (int i = 1; i < MAX_DATA; i++) cnt[i] += cnt[i - 1];
    for (int i = n - 1; i >= 0; i--) {
        ans[cnt[data[i]]-1] = data[i];
        cnt[data[i]]--;
    }
    for (int i = 0; i < n; i++) data[i] = ans[i];
}

int main() {
    int n;;

    cin >> n;

    for (int i = 0; i < n; i++) cin >> list[i];

    counting_sort(list, n);

    for (int i = 0; i < n; i++) cout << list[i] << '\n';
}

 

위의 방식으로 계수 정렬을 구현할 수도 있지만, 정렬할 수가 많아지면 그만큼 메모리를 많이 사용하게 된다.

 

아래의 방법으로 메모리를 좀 더 적게 사용할 수 있다.

#include <iostream>
using namespace std;

int main() {
    int n, a, count[10001] = { 0, };

    cin >> n;

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

    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < count[i]; j++) {
            cout << i << "\n";
        }
    }
}