counting sort (1) 썸네일형 리스트형 34. Counting Sort 앞에서 설명한 정렬 기법들은 데이터끼리 서로 비교하면서 정렬을 수행하는데, 이 방법으로는 시간복잡도가 $\Theta(n\text{ lg }n)$보다 작게 할 수 없다. 하지만 데이터의 범위에 제약이 있는 경우 $\Theta(n\text{ lg }n)$보다 작은 시간복잡도로 정렬을 수행할 수 있다. 그 중 가장 대표적인 방법이 계수 정렬(카운팅 정렬, Counting Sort)이다. 계수 정렬은 각각의 원소가 등장하는 횟수를 센 뒤 앞에 나오는 원소부터 그 원소가 등장하는 횟수만큼 나열하는 것이다. 이 방법은 정렬할 원소의 범위가 크지 않을 때만 쓸 수 있다. 카운팅 정렬의 간단한 구현은 다음과 같다. #import using namespace std; int n,a[100005],p[100005]; in.. 이전 1 다음
