Counting Sort (with JavaScript)

# Counting Sort

Counting Sort는 제한적인 사용 조건을 가진 대신 매우 빠른 정렬 알고리즘으로 non-comparison sort algorithm이다.

O(n + k)의 시간 복잡도를 가지며 comparison sort 범주에 속하는 sorting algorithm보다 빠르다.

다만, k는 데이터의 범위를 나타내는 변수로, 데이터의 수는 적은데 범위만 매우 크다면 다른 알고리즘을 사용하는 것이 현명하다.

또한, count sort는 input data의 크기와 범위에 비례하는 추가 메모리가 필요하므로 메모리에 제약이 있는 상황에서도 사용하기가 어렵다.

 

Counting Sort를 사용하기 위해선 데이터가 다음 조건에 맞아야 한다.

• 항상 양의 정수여야 한다. (따라서 실수 자료형인 경우 사용 불가)
• 데이터의 크기 범위가 제한되어있어야 한다. (최댓값을 알 수 없는 경우 사용 불가)
• 일반적으로 데이터의 범위가 1,000,000을 넘지 않을 때 효과적이며, 제한된 범위 내에 중복 데이터가 많은 경우 효과적이다.

 

# Process

• Input의 범위만큼의 크기를 가지는 count array를 생성한다. Input의 value는 count array의 key가 되며, count array의 value는 데이터 내에서 key가 등장한 횟수이다.
• Input을 순회하며 count array에 값을 채운다.
• count array를 순회하며 result array에 value의 수만큼 key를 채운다.

 

# JavaScript로 구현

// counting sort
function countSort(input) {
  const min = Math.min(...input);
  const max = Math.max(...input);

  // input array의 value를 key로 하는 count array 작성
  const count = new Array(max - min + 1).fill(0);
  for (let i = 0; i < input.length; i += 1) {
    count[input[i] - min] += 1;
  }

  // count array를 result로 변환
  let idx = 0;
  const result = new Array(input.length);
  for (let i = 0; i < count.length; i += 1) {
    for (let j = 0; j < count[i]; j += 1) {
      result[idx] = i + min;
      idx += 1;
    }
  }
  return result;
}