[Algorithm] 계수 정렬 (Counting Sort)

계수 정렬 (Counting Sort)

• 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때, 효과적이고 빠른 정렬 알고리즘이다.
• 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. 
• 카운팅 정렬이라고 하기도 한다.
• 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다.

 

계수 정렬의 조건

1. 데이터의 크기 범위가 제한된 경우
   
   • ex) 0 ~ 100 까지의 점수를 정렬하는 경우
   • 숫자가 클 수록, count를 숫자만큼 만들어야하므로, 메모리 낭비가 심하기 때문이다.
2. 데이터가 양의 정수인 경우
   • 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함
3. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우
   • 필수적인 조건은 아니지만 차이가 클 수록 메모리의 사용이 많아짐

 

프로세스

1. 정렬하고자 하는 배열의 최댓값을 구한다.
2. 최댓값 크기의 배열에 각 원소를 순회하며, 해당 값이 몇 개 인지 저장한다.
   • 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
3. 증가된 리스트에서 0인 값을 제외하고, 인덱스를 인덱스 값만큼 출력

 

ex)

const numbers = [5,2,3,1,4,2,3,5,1,7];
const max = Math.max(...numbers);

const array = new Array(max + 1);
array.fill(0);

for (let i = 0; i < numbers.length; i++) {
  array[numbers[i]]++;
}

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

• 이 때 각 원소의 개수를 카운팅 하기 위해서 원소 중에 가장 큰 수 + 1의 배열 array를 만들어서 모두 0으로 채워주고
  • (+1을 하는 이유는 0부터 저장하기 위함, 그리고 배열의 인덱스를 헷갈리지 않기 위함)
• 정렬해야 할 수들을 반복문으로 돌면서, 정렬해야 할 수를 array의 인덱스로 넣어서 증가시키면 된다. 예를 들어 맨 처음 수가 5라면 array[5]++ 해주면 되는 것이다.
• 그렇게 하면 array에는 각각 수들의 개수가 저장이 되는데, 그만큼을 또 반복문을 돌면서 나열해주면 된다.

 

복잡도

계수 정렬은 배열에 있는 원소들의 개수만 세고 작은 수부터 나열하므로 시간 복잡도는 O(n)이다. 조금 더 구체적으로 보자면 시간 복잡도는 O(n + k)이다. 이때, k는 배열에 있는 최댓값이다.

그리고 공간 복잡도는 k만큼의 배열을 추가로 만들어야 하기 때문에 O(k)이다.

• 시간 복잡도 : O(n + k)
• 공간 복잡도 : O(k)

 

장점

• 데이터의 범위가 작을 때는 O(n)의 시간 복잡도를 가지므로 매우 빠르다

단점

• 데이터의 범위가 크면 만들어야 하는 배열의 크기가 크므로 메모리의 낭비가 심하다