[알고리즘] Counting Sort (계수정렬) 이란? (C++로 구현하기)

계수정렬 (Counting Sort) 이란?

굉장히 빠른 속도를 자랑하는 정렬 (Sort) 이다.

배열에 들어있는 원소의 최대값을 k 라고 가정하면

O(k + n) 의 시간복잡도로 정렬할 수 있다. 그러므로 최선의 경우에서는 퀵정렬보다도 빠르다.

하지만 k 값이 클 경우, 예를 들어서 배열 내의 원소의 최대값이 매우 큰 숫자일 경우 비효율적인 알고리즘이다.

그러므로 배열 내의 원소의 값이 간단한 경우 (예, 1~2자리의 숫자) 에 효율적인 알고리즘이다.

 

 

 

실행 과정

계수정렬은 배열 내에 속해있는 모든 원소를 인덱스로 가지는 배열을 생성한다.

그리고, 각각의 인덱스에 배열 내의 원소가 몇번 들어가는지 계산한다.

 

아래와 같은 정렬하기 원하는 배열이 있다고 가정하자.

 

정렬하기 원하는 배열

 

배열 내의 각 원소가 몇번 나오는지 계산하기 위해 다음과 같이 Counting 배열을 생성한다.

 

Counting 배열

여기에서, Counting 배열의 인덱스는 왜 9 까지일까?

이는 정렬을 원하는 배열의 최대값이 9 이기 때문이다.

 

이제, 정렬하기 원하는 배열에서 각 인덱스가 몇번 발생하는지 계산하여

Counting 배열에 저장한다. 아래와 같이 말이다.

 

원 배열에서 3이 1번, 5가 2번, 8과 9가 1번 발생했기 때문에

위와 같이 저장되었다.

 

이 상태에서 Counting 배열의 각각의 인덱스에, 지난 인덱스의 값을 더해준다. (누적합)

이는 최종 정렬된 배열을 생성하는 과정에서 인덱스를 손쉽게 참조하기 위함이다.

이러한 과정을 거치면 아래와 같은 상태가 된다.

 

그리고 난 후, Counting 배열에 존재하는 각각의 값들의 인덱스를 참고하여

아래와 같이 정렬된 배열을 만들어주면 된다.

 

정렬된 배열

 

 

구현 (C++)

#include <iostream>

using namespace std;

void counting_sort(int* arr, int size)
{
	int* counting, *sorted;
	int maxNum = 0;
	for (int i = 0; i < size; i++) if (arr[i] > maxNum) maxNum = arr[i];
	counting = new int[maxNum + 1]{0};
	sorted = new int[size] {0};

	for (int i = 0; i < size; i++) counting[arr[i]]++;
	for (int i = 1; i <= maxNum; i++) counting[i] += counting[i - 1];
	for (int i = 0; i < size; i++)
	{
		sorted[counting[arr[i]] - 1] = arr[i];
		counting[arr[i]]--;
	}
	for (int i = 0; i < size; i++) arr[i] = sorted[i];

	delete[] counting;
	delete[] sorted;
}

int main(void)
{
	int arr[10] = { 5, 9, 8, 3, 5, 4, 6, 12, 2, 4 };

	for (int i = 0; i < 10; i++) cout << arr[i] << " ";
	cout << '\n';

	counting_sort(arr, 10);

	for (int i = 0; i < 10; i++) cout << arr[i] << " ";
	cout << '\n';

	return 0;
}