계수 정렬(Counting Sort)

/

Comparison Sort

N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N! 이다

따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도이다)

이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것

/

 

Counting Sort 과정

시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값

공간 복잡도 : O(k) -> k만큼의 배열을 만들어야 한다.

Counting이 필요 : 각 숫자가 몇 번 등장했는지 센다.

 

JavaScript 코드

function countingSort(arr, min, max) {
  let i, j = 0;
  const count = [];

  for (i = min; i <= max; i++) {
    count[i] = 0;
  }
  for (i = 0; i < arr.length; i++) {
    count[arr[i]]++;
  }
  for (i = min; i <= max; i++) {
    while (count[i] > 0) {
      arr[j] = i;
      j++;
      count[i]--;
    }
  }
  return arr;
}

• 첫번째 for문에서 0으로 카운트 배열 초기화.
• 두번째 for문에서 각 요소의 발생 횟수를 계산합니다.
• 마지막 for문에서 출력 시퀀스에서 각 요소의 올바른 위치를 포함하도록 카운트 배열 수정.

 

• 사용 : 정렬하는 숫자가 특정한 범위 내에 있을 때 사용
  (Suffix Array 를 얻을 때, 시간복잡도 O(nlgn)으로 얻을 수 있다.)
• 장점 : O(n) 의 시간복잡도
• 단점 : 배열 사이즈 N 만큼 돌 때, 증가시켜주는 Counting 배열의 크기가 크다.
  (메모리 낭비가 심하다)

* 틀린 부분이 있다면 말씀 부탁드립니다!