조건을 만족할때 매우 빠른 정렬 - counting sort

1. counting sort(카운팅 정렬) 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘 하지만 제한사항이 있다 정수나 정수로 표현할 수 있는 자료에 대해서만 적용가능하다 - 각 항목의 발생 횟수를 기록하고자 정수로 인덱스 되는 카운팅 배열을 사용하기 때문 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야한다. 전제조건이 중요함 예를 들어 "0에서 1000이하의 정수이다" 이런 제한조건을 알고 있어야함 음수있으면 안된다는데.. 있어도 될것 같기는 한디 시간복잡도는 O(n+k)의 선형시간(n은 리스트의 길이, k는 정수의 최댓값) 2. 알고리즘 과정 2-1) 주어진 리스트에 등장하는 정수들이 각각 몇개 ..