Counting Sort(계수 정렬)

Counting Sort는 특정 숫자의 범위에서만 숫자의 갯수를 세는 알고리즘입니다. 따라서 데이터는 한번만 접근하면 됩니다.

Counting Sort는 전체 데이터를 한번씩 훑고 지나가면서 갯수만 세어주면 되기 때문에 big-oh는 O(N)입니다.

Counting Sort Code

#include <iostream>

int main()
{
	int count[6] = {0};
	int data[] = {1, 2, 4, 1, 5, 3, 4, 1, 2, 4, 
				  5, 3, 3, 2, 5, 2, 1, 4, 3, 2, 
				  4, 5, 3, 2 ,4, 1, 1, 2, 4, 3};
	
	for(int i = 0 ; i < 30 ; i++)
	{
		count[data[i]]++;
	}	
	
	for(int i = 1 ; i <= 5; i++)
	{
		if(count[i] != 0)
		{
			for(int j = 0 ; j < count[i] ; j++)
			{
				std::cout<< i;
			}
		}
	}
	return 0;
}

이미지 출처
자료 출처