계수 정렬(Counting Sort)

먼저, 계수 정렬은 '범우 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘

얼마나 빠르냐면 시간 복잡도가 O(N)

 

계수 정렬은 크기를 기준으로 세는 알고리즘

 

Ex)

{1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5, 1, 2, 1, 1, 1};

예를 들어 이런 배열을 정열한다고 생각합시다.

 

보이는 배열의 데이터들은 5이하이다. 

 

그래서 1의 개수를 세고, 2의 개수를 세고, ,,, 5의 개수까지 세서

 

새롭게 출력해주는 것이다.

 

#include <stdio.h>

int main(void)
{
	int temp;
	int count[5];
	int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 
				  3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
				  3, 1, 4, 3, 5, 1, 2, 1, 1, 1};

	for (int i = 0; i < 5; i++)
	{
		count[i] = 0;
	}

	for (int i = 0; i < 30; i++)
	{
		count[array[i] - 1]++;
	}

	for (int i = 0; i < 5; i++)
	{
		if(count[i] != 0 )
		{
			for (int j = 0; j < count[i]; j++)
			{
				printf("%d ", i+1);
			}
		}
	}
}

 

코드는 이렇게 되고 있다. 그러나 코드를 보면 데이터의 기준 값만큼 배열을 선언해주고 있다. 

메모리는 진짜 가변적으로 커질 수 있다는 점이 보이고있다.

 

그리고 특정할 때만 정렬을 할 수 있어, 한정적으로 사용할 수 있다.