Counting Sort (계수 정렬)

정렬에는 계수 정렬뿐 아니라 다른 정렬도 많지만 최근에 백준에서 정렬에 대한 문제를 풀다가 'Counting Sort'를 알게 되어 계수 정렬에 대해 정리를 하고 싶어서 이 글을 쓰게 되었다.

Counting Sort이란 ?

카운팅 정렬은 숫자끼리 비교하는 것이 아닌 각 항목의 개수를 세어 저장해두고 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘이다. 시간 복잡도는 𝚶(𝑛)이며 매우 좋은 성능을 보여준다.( 시간 복잡도​에 대해서 따로 공부해서 포스팅 하겠다.)

하지만 좋은 성능을 가진 만큼 제한 사항이 존재한다.

• 정수나 정수로 표현할 수 있는 자료에 한해서 적용 가능.
• 각 항목을 카운트하기 위한 충분한 공간을 할당하려면 배열 내에서 가장 큰 정수를 알아야 함.

정렬 방법 

arr 배열에 들어있는 값들을 예로 오름차순으로 정렬하는 과정을 설명하겠다.

먼저 arr 배열에 들어있는 수의 범위는 최소 1부터 최대 9까지이다. 각 숫자의 개수를 살펴보면 아래와 같다. 

count 배열을 보면 각 값이 몇 개씩 들어있는지 한 눈에 알 수 있다. 

1의 개수는 2개이고 2의 개수는 2개 .... 9의 개수는 1개가 있다.

 

count 배열에 있는 값(= 개수)를 누적합으로 변환하겠다. 누적합으로 변환하는 이유는 밑에서 설명하겠다.

우리는 여기에서 작은 수고를 해서 구한 누적합을 result 배열의 인덱스로 사용할 것이다.

위 그림을 설명하자면 미리 말했듯이 누적합을 result 배열의 인덱스로 사용한다고 하였다. 배열에서 인덱스는 0부터 시작이기 때문에 누적합을 인덱스로 받을 때 -1을 한 상태로 넣어주고 안정적으로 정렬을 하기 위해 마지막 인덱스부터 시작하는 것이 좋다고 한다. 

result 배열의 결과를 보면 count의 값이 result의 값으로 들어가고 (누적합 - 1) 까지 인덱스로 들어가면서 오름차순으로 정렬되어있는 모습을 볼 수 있다.