계수 정렬(Count Sort)
정의
특정 조건이 부합할 때는 매우 빠른 정렬 알고리즘입니다.
특정 조건이란?
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때
에 사용할 수 있습니다.시간복잡도는
O(N+K)
로, K는 데이터 중 최댓값입니다. 따라서 데이터의 크기가 제한되어 있다면 데이터 개수가 많더라도 빠르게 동작합니다.범위 제한
실수형 데이터인 경우 값이 무한한 범위를 가지므로 사용하기 어렵습니다.
적절한 크기 범위
일반적으로 크기 범위가 1,000,000을 넘지 않을 때(가장 큰 데이터 - 가장 작은 데이터 차이가 백만을 넘지 않을때) 효율적으로 사용할 수 있습니다.
왜 크기 범위가 제한되어 있어야 좋을까요?
모든 범위를 담을 수 있는 크기의 배열이 필요하기 때문
(예: max - min 차이가 A라면 A+1개의 크기의 배열이 필요함. A+1개의 숫자가 범위에 포함되어 있기 때문)
방법
먼저 MAX와 MIN의 범위가 모두 담길 수 있도록 배열을 생성합니다.
위 배열을 보면 가장 큰 데이터는 '9', 가장 작은 데이터는 '0'입니다.
그럼 0~9를 모두 포함할 수 있도록 크기가 10인 배열을 선언해야 합니다.
그리고 입력 배열을 돌면서 카운팅을 합니다.
카운트한 배열
01234567892
2
2
1
1
2
1
1
1
2
그럼 카운트한 배열의 처음부터 돌면서 개수만큼 출력하면 정렬한 결과가 될 것입니다.
소스 코드
복잡도
시간 복잡도
위 소스 코드를 보면, 계수 정렬의 시간복잡도는 O(N+K)입니다. 조건만 맞는다면 기수 정렬(Radix Sort)와 함께 가장 빠른 정렬이라고 할 수 있습니다. 단, 기수 정렬은 계수 정렬에 비해 처리할 수 있는 정수의 크기는 더 크고 좀 더 느립니다. (하지만 소스코드가 더 복잡해서 코딩테스트에서 반드시 기수 정렬을 이용해야만 해결할 수 있는 문제는 거의 출제되지 않는다고 합니다.)
공간 복잡도
데이터의 범위가
1,000,000,000
이라면? 카운팅 배열을 int로 선언한다면, 4byte가 1,000,000,000개 필요합니다∴ 4GB의 공간이 필요합니다. 따라서 사용할 수 없습니다.
예를 들어 입력 데이터가 [0, 9, 0, 9, 0, 9, ....] 등 0과 9로만 이루어져있다고 합시다. 그러면 0과 9만 카운팅하면 되지만, 배열은 크기가 10으로 선언해야 합니다. 따라서 데이터에 따라 비효율적일 수가 있습니다.
그러므로 항상 쓸 순 없고, 범위가 제한되어 동일한 값을 가지는 데이터가 여러 개 등장할 때 효율적입니다. 따라서 데이터 특성을 파악하기 어렵다면 퀵 정렬(대부분 정렬 라이브러리도 퀵 정렬과 비슷한 식으로 구현)이 가장 유리한 것입니다.
참고
이것이 취업을 위한 코딩테스트다 (나동빈)
Last updated