계수 정렬

계수 정렬은 값을 비교해서 정렬하지 않습니다. 모든 값이 예를 들어 1부터 40 사이의 정수라는 것을 안다면, 각 값이 몇 개인지 세기만 하면 그 개수로 각 값이 들어갈 자리를 계산할 수 있습니다. 범위가 좁다면 이보다 빠른 정렬은 거의 없습니다.

목록의 막대들, 각 값이 몇 번 나오는지 보여 주는 카운터 띠, 그리고 값마다 자기 구간이 있는 버퍼 행
목록의 막대들, 각 값이 몇 번 나오는지 보여 주는 카운터 띠, 그리고 값마다 자기 구간이 있는 버퍼 행

세기

가장 작은 값과 가장 큰 값을 찾아, 그 사이의 모든 값마다 카운터를 하나씩 만들고 모두 0에서 시작합니다. 목록을 처음부터 끝까지 한 번 읽으며, 보이는 값의 카운터에 1을 더합니다. 이제 카운터들은 히스토그램이 됩니다: 1이 몇 개, 2가 몇 개 하는 식입니다. 값이 n개, 카운터가 k개라면 이 과정에 n단계가 걸립니다.

더하기

가장 작은 값과 같은 값들이 맨 앞에 오므로 그 구간은 1번 자리에서 시작합니다. 다음 값의 구간은 그 바로 뒤에서 시작하고, 나머지도 마찬가지입니다: 각 구간은 앞선 모든 개수의 합 다음에서 시작합니다. 누적 합이라고 부르는 이 합계들이 히스토그램을 정렬된 목록의 지도로 바꿉니다. 이 과정에 k단계가 걸립니다.

놓기

목록을 한 번 더 읽으며 모든 값을 자기 구간의 다음 빈자리로 옮깁니다. 값을 나타난 순서대로 옮기므로 같은 값은 원래 순서를 유지합니다: 계수 정렬은 안정 정렬입니다. 버퍼를 다시 복사하면 목록이 정렬됩니다. 앱에서는 값이 놓일 때마다 각 카운터가 다시 줄어드는 모습을 보여 줍니다.

예시

4, 1, 3, 4, 2, 1, 4를 예로 들어 봅시다. 1부터 4까지의 카운터는 최종적으로 2, 1, 1, 3이 됩니다. 차례로 더하면 구간이 정해집니다: 1들은 1번과 2번 자리, 2는 3번 자리, 3은 4번 자리, 4들은 5번부터 7번 자리입니다. 값을 목록 순서대로 놓으면 1, 1, 2, 3, 4, 4, 4가 됩니다: 센 값 7개, 이동 14번, 카운터 4개, 비교는 없습니다.

언제 쓸까

전체 작업량은 n + k에 비례합니다. 0부터 100까지의 시험 점수 천 개처럼 k가 n에 비해 작으면, 계수 정렬은 약 n log₂ n번 비교해야 하는 어떤 비교 정렬보다도 빠릅니다. 범위가 넓으면 낭비가 큽니다: 백만까지 흩어진 값 몇 개에 카운터 백만 개가 필요합니다. 기수 정렬은 자릿수마다 계수 정렬을 한 번씩 실행해 이 문제를 해결하므로, 패스마다 카운터 열 개만 있으면 됩니다. Harold Seward는 1954년에 기수 정렬과 함께 계수 정렬을 설명했습니다.

직접 해 보기

앱을 열고 ‘단계’를 누르세요. 목록과 버퍼 행 사이의 띠에 값마다 카운터가 하나씩 보입니다. 목록을 읽는 동안 카운터가 채워지고, 개수를 더하면 버퍼에 구간이 나타나며, 값이 놓일 때마다 카운터가 다시 줄어드는 모습을 지켜보세요. 값 종류가 적은 목록을 고르면 큰 구간을, 서로 멀리 떨어진 숫자를 입력하면 넓은 범위에 카운터가 얼마나 많이 필요한지 볼 수 있습니다.

자주 묻는 질문

계수 정렬의 시간 복잡도는?

값 n개와 가능한 값 k개에 대해 O(n + k)이며, 카운터와 버퍼에 O(n + k)의 추가 메모리가 필요합니다.

계수 정렬이 항상 가장 빠르지 않은 이유는?

비용이 값의 개수뿐 아니라 값의 범위에도 달려 있기 때문입니다. 범위가 목록보다 훨씬 넓으면 대부분의 카운터가 0에 머물고, 시간과 메모리가 낭비됩니다.

계수 정렬로 음수도 정렬할 수 있나요?

네. 카운터는 가장 작은 값부터 가장 큰 값까지 이어지므로, 가장 작은 값을 빼면 카운터의 인덱스가 됩니다. 앱도 같은 방식입니다.

계수 정렬은 안정 정렬인가요?

네, 값을 목록 순서대로 자기 구간의 다음 빈자리로 옮기기만 하면 됩니다. 기수 정렬은 이 성질에 기대고 있습니다.

시도해 볼 준비가 되셨나요?

브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

계수 정렬 해 보기