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

백준 알고리즘 문제를 풀다보니 기본 정렬 알고리즘 외에도 정렬 알고리즘이 있다는 것을 알게되어 정리해보고자 한다.

계수 정렬(Couting Sort)이란?

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

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

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

기본 로직

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

2. 배열 A를 처음부터 순회하면서 원소 값에 해당하는 배열 B의 인덱스의 원소 값 +1
   

3. 결과 출력(누적 합이 필요하면 과정 추가 필요)
   

정리

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

위 3가지 조건을 만족하는 경우에 계수 정렬을 사용해야겠다.

카운팅 정렬 관련 백준 문제

10989번 수 정렬하기3(with. JAVA)