계수정렬

• 정의
  • 데이터 값의 갯수를 count해 그 데이터가 얼마나 있는지를 알 수 있는 정렬 알고리즘이다
• 조건
  • 데이터가 양수만 존재해야 한다
  • 데이터의 크기가 매우 작아야한다
• 핵심
  • 
  • 주어진 수의 +1만큼 배열을 미리 만들어 준다
  • 입력받은 값에 속하는 index번지에 count를 +1씩 해준다
  • 출력시 배열이 0 이 아닌 index에 count한 수만큼 index를 출력해준다
• 구현

#include <iostream>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n{};
	int input{};
	int arr[10001]{};
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> input;
		arr[input]++;
	}

	for (int i = 0; i < 10001; i++)
	{
		if (arr[i] != 0)
		{
			for (int j = 0; j < arr[i]; j++)
			{
				cout<<i<<"\n";
			}
		}
	}
}