계수 정렬이란?
합병 정렬, 퀵 정렬 등의 기본 정렬 알고리즘과 달리 숫자를 비교하는 작업이 없이 각 항목의 개수를 카운트하여 정렬하는 알고리즘이다. 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 수행하며, 주어진 배열의 값 범위가 작은 경우에 빠른 속도로 정렬이 가능하다.
자료의 범위를 알고 있으며, 정렬할 값이 정수일 때 사용한다.
기본 로직
1. 입력 배열의 최댓값을 크기로 하는 Counting Array 생성
카운팅 배열의 모든 원소 값을 0으로 초기화
*필요에 따라 결과를 출력할 배열도 따로 생성
2. 입력 배열 원소 개수의 누적합
입력 배열을 처음부터 순회하면서 원소 값에 해당하는 배열의 인덱스의 원소값을 카운팅(+1)한다.
3. 입력 배열과 누적합 배열을 이용한 정렬 수행
입력 배열의 각 원소에 대해 만들어둔 카운팅 배열을 조회하여 어느 인덱스로 접근해야 하는지 체크한 후, 조회한 원소의 개수를 1씩 감소하며 바로 앞의 인덱스로 올 수 있도록 한다.
시간복잡도 : O(N+K)
- K = 배열 내 최댓값
- K가 커질수록 무한대에 가까워져 성능이 떨어진다. ⇒ 입력값의 범위가 작을 때 높은 효율을 보인다.
최댓값이 주어지지 않은 경우, 전체 배열을 탐색해야 하므로 O(n), Counting Array에 개수를 카운팅하는 과정에서 O(n)이 소요된다. 이후 결과 배열에 값을 입력하여 정렬된 배열을 얻는 과정에도 O(n)이 소요되어 최종적으로 O(n)의 시간복잡도를 가지며, 정렬 시간은 K에 종속된다.
참고 자료
서버 개발자를 꿈꾸며 성장하는 쭌입니다 😽