정렬에는 계수 정렬뿐 아니라 다른 정렬도 많지만 최근에 백준에서 정렬에 대한 문제를 풀다가 'Counting Sort'를 알게 되어 계수 정렬에 대해 정리를 하고 싶어서 이 글을 쓰게 되었다.
Counting Sort이란 ?
카운팅 정렬은 숫자끼리 비교하는 것이 아닌 각 항목의 개수를 세어 저장해두고 그에 따라서 적절한 위치에 정렬하는 효율적인 알고리즘이다. 시간 복잡도는 𝚶(𝑛)이며 매우 좋은 성능을 보여준다.( 시간 복잡도에 대해서 따로 공부해서 포스팅 하겠다.)
하지만 좋은 성능을 가진 만큼 제한 사항이 존재한다.
- 정수나 정수로 표현할 수 있는 자료에 한해서 적용 가능.
- 각 항목을 카운트하기 위한 충분한 공간을 할당하려면 배열 내에서 가장 큰 정수를 알아야 함.
정렬 방법
arr 배열에 들어있는 값들을 예로 오름차순으로 정렬하는 과정을 설명하겠다.
먼저 arr 배열에 들어있는 수의 범위는 최소 1부터 최대 9까지이다. 각 숫자의 개수를 살펴보면 아래와 같다.
count 배열을 보면 각 값이 몇 개씩 들어있는지 한 눈에 알 수 있다.
1의 개수는 2개이고 2의 개수는 2개 .... 9의 개수는 1개가 있다.
count 배열에 있는 값(= 개수)를 누적합으로 변환하겠다. 누적합으로 변환하는 이유는 밑에서 설명하겠다.
우리는 여기에서 작은 수고를 해서 구한 누적합을 result 배열의 인덱스로 사용할 것이다.
위 그림을 설명하자면 미리 말했듯이 누적합을 result 배열의 인덱스로 사용한다고 하였다. 배열에서 인덱스는 0부터 시작이기 때문에 누적합을 인덱스로 받을 때 -1을 한 상태로 넣어주고 안정적으로 정렬을 하기 위해 마지막 인덱스부터 시작하는 것이 좋다고 한다.
result 배열의 결과를 보면 count의 값이 result의 값으로 들어가고 (누적합 - 1) 까지 인덱스로 들어가면서 오름차순으로 정렬되어있는 모습을 볼 수 있다.
'문제풀이 > 알고리즘' 카테고리의 다른 글
시간 복잡도(Time Complexity) (0) | 2022.03.25 |
---|