입력 되는 수가 음이 아닌 정수일 때 수들을 정렬하는 count sort 에 대해 알아보자.

정렬 방법 중에 가장 빠른 방법 이다.... 시간 복잡도 : O(n)

아래와 같은 단점이 있지만 이 소트 방법도 알겸 배열처리도 공부할 겸 좋은 문제.

• 수들이 실수이거나
• 수들의 산포(흩어진 정도)가 큰 경우 많은 메모리를 사용해야 하는 단점

준비

• ia[] 데이터 배열
• ib[] 임시처리 배열
• ic[] 답 배열

1. 소트대상이 되는 배열 ia[] 중 가장 큰 데이터가 9 이므로 배열 ib[] 는 9 개의 공간을 마련한다.

   

2. 배열 ia[] 를 순차적으로 읽으면서 6 이라면 ib[] 배열의 6 번째 원소에 1 을 누적하고, 2 이면 2 번째 원소에 1 을 누적,...

   

3. 배열 ib[] 를 차례대로 누적한다.
   
4. 배열 ia[] 의 6 의 위치는 , ib[6] 즉 4 번째이므로 , ia[4] 를 ic[ib[4]] 에 위치 후 4 를 1 감소한다.( 1 감소하는 이유는 배열 ia[] 에 6 이 한 번 이상 나올수 있기 때문)
   

입력

입력의 첫 줄은 데이터의 개수 이고 , 다음 줄 부터 데이터가 입력된다.

출력

입출력 예

입력

7
6 2 9 8 3 4 7

출력

2 3 4 6 7 8 9