[알고리즘] 계수 정렬 (Counting Sort)

[알고리즘] 계수 정렬 (Counting Sort)

---

특정한 범위 내에 속해있다면 O(NlogN)의 기존 정렬들보다 빠른 O(N)의 시간복잡도를 가질수 있는 알고리즘으로 단순하게 크기를 기준으로 세는 알고리즘이다.

크기를 기준으로 갯수를 세보자!!!

다음 숫자들을 오름차순으로 정렬하는 프로그램을 작성하자!

5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5

위의 숫자들은 5이하의 숫자라는 범위안에 들어가 있다.

---

 

5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5

1	2	3	4	5
0	0	0	0	0

5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5

1	2	3	4	5
0	0	0	0	1

5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5

1	2	3	4	5
1	0	0	0	1

---

5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5

1	2	3	4	5
3	2	3	2	2

그 후 해당 원소의 갯수만큼 출력하면 된다.

1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5

소스코드 구현 (C++)

#include <iostream>
using namespace std;
int main()
{
	int arr[12] = { 5, 1, 3, 4, 2, 1, 2, 3, 4, 1, 3, 5 };
	int temp;
	int count[5] = { 0, 0, 0, 0, 0 };

	//계수 배열
	for (int i = 0; i < 12; i++)
	{
		count[arr[i] - 1]++;
	}

	//정렬
	int num = 0;
	for (int i = 0; i < 5; i++)
	{
		int size = count[i];
		int index = i + 1;
		if (size != 0)
		{
			for (int j = 0; j < size; j++)
			{
				arr[num] = index;
				num++;
			}
		}
	}

	cout << "Counting Sort = [";
	for (int i = 0; i < 10; i++)
	{
		if (i != 9) cout << arr[i] << ", ";
		else cout << arr[i];
	}
	cout << "]" << endl;
	return 0;
}

출력 결과

시간 복잡도 계산

한번의 반복문으로 배열을 훑으면서 해당 개수의 숫자만 카운팅하기 때문에 N이 소요되는 알고리즘이다.

즉, 시간복잡도는 O(N)이다.

---

아주 빠른 정렬알고리즘이지만 데이터의 갯수가 한정되어있을 때라는 제한이 따르기 때문에 자주 사용은 안하는 알고리즘이라고 한다.