[알고리즘] 계수 정렬(Counting Sort)

계수 정렬(Couting Sort)이란?

• 카운팅 정렬은 각 항목이 몇 개 있는지 카운트하는 정렬
• 기본 정렬 알고리즘과 다르게 숫자 비교 작업이 없음(카운트만 할 뿐)
• 자료의 범위를 알고 있으며, 정렬할 값이 정수일 때 사용

 

시간 복잡도: O(N+K)

• K = 자료 안 가장 큰 원소값
• K가 작으면 문제가 없지만, K가 커질수록 무한대에 가까워질 수 있음

 

기본 로직

1. 정렬할 배열(배열 A)와 카운팅한 숫자를 저장할 배열(배열 B)을 생성
   • 배열 B의 크기는 배열 A 원소들 중 가장 큰 값
   • 배열 B은 모든 원소 값을 0으로 설정
   • 필요에 따라 결과를 출력할 배열을 따로 생성

1. 배열 A를 처음부터 순회하면서 원소 값에 해당하는 배열 B의 인덱스의 원소 값 +1
   
2. 결과 출력(누적 합이 필요하면 과정 추가 필요)
   

 

정리

1. 정렬할 값이 정수
2. 자료의 범위를 알고 있음
3. 알고 있는 자료의 범위가 너무 크지 않음