계수정렬(counting sort)

알고리즘 문제를 풀다가 계수정렬(counting sort)의 개념을 잘 몰라서 공부할 겸 정리 해 보았다.

계수정렬(counting sort)이란?

계수정렬은 숫자들 간 비교를 하지 않고 정렬을 하는 알고리즘이다. 숫자를 비교하지 않고 각 숫자들의 개수만 세고 정렬을 진행하기 때문에 시간복잡도는 O(n)이 나온다. 계수정렬의 시간복잡도는 가장 빠르지만 정해진 상황에서만 쓸 수 있다.

1. 배열 내 모든 요소는 정수이어야 한다.
2. 배열 내 모든 요소의 범위는 1 ~ k 이어야 한다.
3. k = O(n) 으로 나타낼 수 있어야 한다.

예제풀이

각 요소들의 범위가 1 ~ 5까지의 범위를 갖는 배열 A가 주어졌을 때 정렬한 후 출력하여라.

k = 5;
A = [1, 2, 2, 3, 1, 4, 5, 2, 3, 3, 3, 2, 1, 1, 1, 5, 2, 1, 3, 4];

계수정렬은 요소들끼리 비교하지 않는다고 했다. 정해진 범위가 있으니 배열을 순회하면서 각 요소의 개수를 counting해주면 된다.

// 1부터 시작하므로 길이는 k + 1이다.
const count = new Array(5 + 1).fill(0);
A.forEach(v => count[v]++);

위 로직을 실행하여 count 변수를 출력해보면 아래와 같이 나오는걸 확인해 볼 수 있다.

[0, 6, 5, 5, 2, 2]

이제 남은 작업은 count 변수를 순서대로 돌면서 counting된 요소의 개수만큼 출력만 하면 된다.

for (let i = 1; i < count.length; i++) {
  for (let j = 0; j < count[i]; j++) {
    console.log(i);
  }
}

출력된 결과는 아래와 같다.

Reference

https://devjin-blog.com/sort-algorithm-8/