[JS] 계수 정렬

1. 계수 정렬

 앞에서 포스팅한 것 중 제일 빠른 알고리즘을 고르자면 O(Nlog₂N)의 속도를 가지는 퀵 정렬, 병합 정렬, 힙 정렬이 있었다. 하지만 이번 포스팅에서는 이 세 개의 정렬보다 더 빠른 속도 O(N)의 속도를 가지는 계수 정렬에 대해서 포스팅하려고 한다. 단, 아래와 같은 조건이 주어졌을 경우다.

 

 

5 4 3 2 1 1 1 1 3 4 5 5 2 2 2

 

다음과 같은 5이하의 원소를 가진 배열의 원소들을 오름차순으로 정렬하시오

 

 

 

2 . 동작 순서

 동작 순서는 다음과 같이 간단하다.

 

1. 1에서 5까지의 원소의 개수를 카운팅한다.

2. 카운팅한 개수만큼 원소들을 나열한다.

3. 끝.

 

그림을 이용해서 설명을 해보도록 하겠다. 밑의 배열을 오름차순으로 정렬하려고 한다.

 

[그림 1] 입력 배열 

5 이하의 모든 자연수의 개수를 세기위해 5라는 크기를 가진 count라는 배열을 만들도록 하자. 

 

[그림 2] Count 배열

 

 인덱스 순으로 count[0]은 1의 개수를, count[1]은 2의 개수를, count[2]은 2의 개수를 세도록 할 것이다. 그런 이유로 모든 원소 값을 0으로 초기화 했다. 이제 입력 배열을 순차적으로 탐색해서 개수를 세주도록 하자. 탐색을 마치면 count 배열은 다음과 같이 업데이트 될것이다.

 

[그림 3] 탐색 후 count 배열

 

 이제 count 배열의 각 원소의 값만큼 인덱스+1의 숫자를 출력해주면 된다. 

 

[그림 4] count 배열의 원소 값 만큼 인덱스 + 1의 수를 출력 

 

 속도는 굉장히 빠르다. 하지만 숫자 중에 1000이라는 숫자가 있다면, count를 1000만큼 만들어야하므로, 메모리 낭비가 심할 것 같다. 상황을 적절히 봐가면서 정렬방법을 쓰도록 하는 것이 중요한 것 같다.

 

 

3. 프로그램 코드

const arr = [5, 4, 3, 2, 1, 1, 1, 1, 3, 4, 5, 5, 2, 2, 2];
const count = Array(5).fill(0);
let sorted = [];

for(let i=0; i<arr.length; i++)
  count[arr[i]-1]++;

for(let i=0; i<count.length; i++){
  const sortedNum = Array(count[i]).fill(i+1); 
  sorted = sorted.concat(sortedNum);
}

console.log(sorted);

 

 

4. 참고 자료

 동빈나 님의 블로그 - 11. 계수 정렬(Counting Sort)