[알고리즘] 정렬 - 계수 정렬 (Counting Sort) (js/javascript/자바스크립트)

정렬 중에 그나마 빠른 힙정렬의 경우에도 시간복잡도 O(Nlog₂N)인데 

계수정렬은 시간복잡도가 O(N)으로 굉장히 빠르다.

💥그러나 정렬해야할 수의 범위가 작을 때에만 유리하다는 것을 유의해야 한다

-> 정렬해야할 수가 0,100,2,10,1000 이라면 고작 5개의 수를 정렬하는데 0부터 1000까지 배열을 만들어야 하기 때문에 메모리가 낭비되고 반복문도 불필요하게 돌아야 한다.

 

방법은 간단하다. 정렬해야 할 수가 [5,2,3,1,4,2,3,5,1,7] 이라면

1. 주어진 원소들을 반복문으로 돌며 각 원소의 개수를 카운팅한다.

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

 

이 때 각 원소의 개수를 카운팅 하기 위해서 원소 중에 가장 큰 수 + 1의 배열 array를 만들어서 모두 0으로 채워주고

(+1을 하는 이유는 0부터 저장하기 위함, 그리고 배열의 인덱스를 헷갈리지 않기 위함)

정렬해야 할 수들을 반복문으로 돌면서, 정렬해야 할 수를 array의 인덱스로 넣어서 증가시키면 된다. 예를 들어 맨 처음 수가 5라면 array[5]++ 해주면 되는 것이다.

그렇게 하면 array에는 각각 수들의 개수가 저장이 되는데, 그만큼을 또 반복문을 돌면서 나열해주면 된다.

 

 

 

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);
    }
  }
}

 

---

 

참고로 백준 10989번을 nodejs로 풀어보려했으나 계수 정렬(counting sort)문제였음에도 불구하고 메모리 초과가 나서 
nodejs로 푼 결과를 보니 맞은 사람이 한 명도 없었다.

nodejs로는 입력을 받아서 그 입력 값을 배열에 저장하는 것 부터 메모리초과라고 나기 때문에 백준에서는 해당 문제를 nodejs로 풀 수 없는 것 같다.