[Algorithm]Sort-Counting Sort

Counting Sort은 배열에서 각 고유 요소의 발생 횟수를 세어 배열을 정렬하는 정렬 알고리즘입니다. 이것은 선형 시간 정렬 알고리즘이며 정수 또는 자연 순서가 있는 다른 값에 사용할 수 있습니다. 카운트 정렬의 기본 개념은 각 입력 요소에 대해 해당 요소보다 작은 요소의 수를 결정하는 것입니다. 이것이 결정되면 요소를 정렬된 배열에 직접 배치할 수 있습니다. 카운트 정렬은 입력 데이터 범위가 정렬할 개체 수보다 크지 않을 때 가장 잘 작동합니다.

카운트 정렬 알고리즘에는 다음 단계로 진행합니다.

1. 입력 배열에서 최대값을 찾습니다.
2. 크기가 max+1인 새 배열을 만들고 모든 요소를 0으로 초기화합니다.
3. 입력 배열을 통과하고 각 요소의 발생을 카운트합니다.
4. 요소의 누적 합계를 포함하도록 카운트 배열을 업데이트합니다.
5. 입력 배열을 오른쪽에서 왼쪽으로 이동하고 각 요소를 출력 배열의 올바른 위치에 배치합니다.
6. 방금 배치한 요소의 개수를 줄입니다.

코드의 예시를 아래와 같아요.

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  const output = [];

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

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

  for (let i = arr.length - 1; i >= 0; i--) {
    output[count[arr[i]] - 1] = arr[i];
    count[arr[i]]--;
  }

  return output;
}

코드를 살펴보면

• Math.max() 메서드를 사용하여 입력 배열에서 최대값을 찾고 변수 max에 저장합니다.

• max+1 크기의 새로운 배열 수를 만들고 모든 요소를 0으로 초기화한다.

• 우리는 입력 배열을 통과하고 각 요소의 발생을 계산한다. 그에 따라 카운트 배열을
  업데이트합니다.
  

• 우리는 요소의 누적 합계를 포함하도록 카운트 배열을 업데이트한다.

• 입력 배열을 오른쪽에서 왼쪽으로 이동하고 각 요소를 출력 배열의 올바른 위치에 배치합니다. 방금 배치한 요소의 개수를 줄입니다.

• 마지막으로 정렬된 배열을 반환합니다.

  예시를 아래와 같습니다.

const arr = [5, 2, 9, 5, 2, 3, 5];
const sortedArr = countingSort(arr);
console.log(sortedArr); // [2, 2, 3, 5, 5, 5, 9]

카운트 정렬은 입력 데이터의 작은 범위에 가장 적합한 간단하고 효율적인 정렬 알고리즘입니다. 이것은 선형 시간 정렬 알고리즘이며 정수 또는 자연 순서가 있는 다른 값에 사용할 수 있습니다.

감사합니다.