[C/C++] 카운팅 정렬 (Counting Sort)

카운팅 정렬 (Counting Sort)

 

카운팅 정렬 (Counting Sort)은 정렬할 수의 범위가 작은 경우 사용하는 정렬으로, 시간 복잡도가 O(n)인 매우 빠른 정렬입니다.

 

단점은 수의 범위가 커지면 사용하는 메모리도 그만큼 커진다는 단점이 있습니다. (이때문에 수의 범위가 작은 경우에 사용)

---

작동 원리

 

카운팅 정렬의 원리는 간단합니다. 정렬할 원소를 하나씩 살펴보고, 그 원소 값에 해당하는 배열에 카운트를 1 늘려주면 됩니다. 

카운팅 정렬 작동 방식 (GIF)

카운팅 정렬이 작동하는 방식을 GIF로 만들어 보았습니다.

 

위의 그림에서는 배열의 크기가 10,000개나 되지만, 실제 입력 값의 최대 크기는 7이므로 그만큼 크기를 줄여도 작동합니다.

 

반대로, 입력값에 100,000,005 같이 큰 수가 나온다면, 그만큼 배열이 커져야 하겠죠?

이런 이유 때문에 카운팅 정렬은 입력값의 범위가 작은 경우에 적합한 정렬입니다.

 

---

사용 예시

 

이해를 돕기 위해 문제 하나를 예시로 풀어보겠습니다. (백준 10989번)

 

[문제]

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

[소스코드]

#include <iostream>
using namespace std;
// [baekjoon] 10989번 - 수 정렬하기 3
// 2023.01.19

int main(void) {

	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n, tmp;
	cin >> n;

	int countArray[10001] = { 0 };

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

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

	return 0;
}

위의 GIF가 이 문제의 입력예시를 가지고 만들어진 이미지 입니다.

입력값의 범위가 1~10000이므로 그에 맞춰서 카운트한 값을 저장할 배열을 만든 후,

카운트 값이 저장된 배열을 원하는 순서대로 확인하면서 값을 출력하면 됩니다.

 

카운팅 정렬을 사용한 결과, 입력값 전체를 담을 배열이 필요하지 않아서 그만큼의 메모리를 절약한다는 장점도 있습니다.