[Algorithm] 정렬 - 계수 정렬 (Counting Sort)

계수 정렬(Counting Sort)이란?

- 데이터 값을 직접 비교하지 않고, 단순하게 개수를 세어 기록하고 정렬하는 방식이다.

- 값 비교가 일어나지 않기 때문에 속도가 매우 빠르다.

- 하지만 개수를 저장하는 배열, 정렬할 배열을 위한 추가 공간이 필요하다.

- 또한 숫자가 매우 큰 경우에는 속도가 현저히 느려질 수 있다.

 

 

작동 방식

1) 데이터 중 제일 큰 수 + 1의 크기로 카운트 배열을 만든다.

   (아래 예시에서는 4 = 크기가 5인 배열 할당)

2) 카운트 배열에 각 숫자가 몇 번 나타나는지 개수를 세어 해당 인덱스에 저장한다.

   (숫자 2는 두 번 나타나므로, 카운트 배열 인덱스 2에 2를 저장)

3) 누적합을 만든다.

   (이 전 숫자를 더한다.)

   누적합이 의미하는 것은 정렬되는 위치이다.

   0의 경우 0~1에 정렬

   1의 경우 1~3에 정렬

   2의 경우 3~5에 정렬

   3의 경우 5~5에 정렬 (3은 데이터가 없으므로 정렬될 필요가 없다.)

   4의 경우 5~6에 정렬

 

4) 배열을 차례로 돌면서, 정렬 위치를 찾아 새 배열에 저장한다.

 

 

---

1. 정리하고 여러 블로그들을 봤는데, 모두 배열 끝 인덱스부터 정렬을 한다.

뒤에서부터 정렬해야 안정정렬이라는 설명도 있는데... 어차피 배열의 처음부터 끝까지 한번 도는 것이니 상관없지 않나?

이 점은 좀 더 찾아봐야겠다.

 

2. 누적합을 굳이 구해야 할까? 0~1 범위에 0, 1~3 범위에 1 이런식으로 정렬해도 될 것 같은데.

 

 

소스 코드

#include <iostream>

using namespace std;

void countingSort(int* arr, int len);

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

	int* arr = new int[N + 1];
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	countingSort(arr, N);

	for (int i = 0; i < N; i++) {
		printf("%d\n", arr[i]);
	}

	delete[] arr;

	return 0;
}

void countingSort(int* arr, int len) {
	int max = 0;
	for (int i = 0; i < len; i++) {
		if (arr[i] > max) max = arr[i];
	}

	int* count = new int[max + 1]{ 0, };
	for (int i = 0; i < len; i++) {
		count[arr[i]]++;
	}

	// 누적합
	for (int i = 1; i <= max; i++) {
		count[i] += count[i - 1];
	}

	int* sort = new int[len];
	for (int i = 0; i < len; i++) {
		int index = --count[arr[i]];
		sort[index] = arr[i];
	}

	for (int i = 0; i < len; i++) {
		arr[i] = sort[i];
	}

	delete[] count;
	delete[] sort;
}

 

 

 

시간복잡도

평균의 경우 : O(n+k)

최선의 경우 : O(n+k)

최악의 경우 : O(n+k)

 

값 비교 없이 단순히 숫자를 세기 때문에 시간복잡도는 O(n+k)로 굉장히 빠르다.

(n : 데이터, k : 계수)

하지만 데이터 값이 매우 큰 경우, k값도 그만큼 커지므로 O(n²), O(n³)이 될 가능성도 있다.