[c++/정렬] 계수정렬 (counting sort, 카운팅 정렬)

사실 계수정렬은 값을 비교해서 정렬하는 방식이라기 보다는 값의 개수를 세고 그 개수에 따라서 위치를 설정해 주는 방식이다. 데이터 간의 크기를 비교하는 정렬은 아니다.

​

대신 굉장히 빠른 속도를 자랑하는 정렬이다. 최선의 경우 퀵정렬보다 빠르다. 하지만 배열에 원소가 많다면 비효율적이다.

​

계수 정렬 동작 원리는

​

다음과 같이 data라는 배열을 정렬한다.

 

int data[20] = { 1,4,2,5,3,2,3,4,5,2,2,2,3,4,1,4,2,5,5,1 };

 

1. 첫 번째로 해야할 일은 각 숫자가 몇 번 나오는지 세는 것이다.

수	1	2	3	4	5
나온 횟수	3	6	3	4	4

 

data 배열에 등장한 수와 그 수가 몇 번 나왔는지 알 수 있다. 

 

2. 그 다음 각 수의 누적합을 구한다.

수	1	2	3	4	5
나온 횟수	3	6	3	4	4
횟수에 대한 누적합	3	9	12	16	20

 

누적합을 통해 각 숫자가 어느 인덱스에 위치해야 하는지 찾을 수 있다.

​

3. 이제 정렬된 배열을 만들면 된다.

1) data 배열을 뒤에서 앞으로 순회한다.

2) data[i] 값의 누적합에 해당하는 위치에 값을 대입한다.

3) data[i] 값이 하나 없어졌으므로 해당 값에 대한 누적합을 1 감소시킨다.

4) 2),3)을 반복한다

 

위에 예시에 대해 일부 과정 진행하면 이렇게 된다.

 

c++로 작성한 코드이다. 

#include <iostream>

#define MAX_SIZE 1000
#define MAX_NUM 10000

using namespace std;

int main()
{
    int N;
    int origin[MAX_SIZE + 1];
    int answer[MAX_SIZE + 1];
    int count[MAX_NUM + 1];
    int count_sum[MAX_NUM + 1];

    cin >> N;
    for (int i = 0; i <= N; i++)
        count[i] = 0;
   
    // Counting
    for (int i = 1; i <= N; i++)
    {
        cin >> origin[i];
        count[origin[i]]++;
    }
  
    // Counting Sum
    count_sum[0] = count[0];
    for (int i = 1; i <= MAX_NUM; i++)
        count_sum[i] = count_sum[i - 1] + count[i];

    // Sorting
    for (int i = N; i >= 1; i--)
    {

        answer[count_sum[origin[i]]] = origin[i];
        count_sum[origin[i]]--;
    }

    for (int i = 1; i <= N; i++)
        cout << answer[i] << " ";
}

 

더 간단한 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;


int main() {
	int count[5] = {};
	int data[20] = { 1,4,2,5,3,2,3,4,5,2,2,2,3,4,1,4,2,5,5,1 };
	//정렬
	for (int i = 0; i < 20; i++) {
		count[data[i] - 1]++;
	}
	//결과 출력
	for (int i = 0; i < 5; i++) {
		if (count[i] != 0) {
			for (int j = 0; j < count[i]; j++) {
				cout << i + 1 << " ";
			}
		}
	}
}