기수 정렬 계수 정렬

계수정렬

Counting sort(계수 정렬)는 각 요소의 배열 등장 횟수를 count해 누적합으로 나타내는 배열을 만든 뒤, 그 누적합으로 요소들의 index를 알아내 작은 숫자 순서대로 정렬하는 기법이다.

비교 정렬이 아니기 때문에 O(n + k) 라는 시간 복잡도를 가진다. k는 Input 요소의 최댓값인데, k가 작은 수라면 O(n)이겠지만, k가 무한으로 커질 때는 O(무한)이 될 수도 있다.

따라서 요소의 최댓값에 영향을 받는 알고리즘이다.
( O(n + k) : n or k 라는 뜻으로, n이 클지 k가 클지 아직 모름 )

앞서 언급했듯, Input arr의 요소 중 최솟값 ~ (최댓값 - 1) 길이 만큼의 누적합 배열(혹은 객체)을 필요로 하는 정렬 기법이므로 요소 간 차이가 크거나, 최댓값 요소가 매우 클 경우 메모리 낭비가 심한 경우가 생길 수 있다.

방법1

function countingSort(arr) {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  let obj = {};

  for (let i = min; i <= max; i++) {
    obj[i] = 0;
  }

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

  let sorted = [];

  for (let i = min; i <= max; i++) {
    while (obj[i] > 0) {
      sorted.push(i);
      obj[i]--;
    }
  }
  return sorted;
}

방법2

function countingSort(arr) {
  let max = Math.max(...arr);
  let countArr = Array(max + 1).fill(0);

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

  let sorted = [];
  for (let i = 0; i < countArr.length; i++) {
    while (countArr[i] > 0) {
      sorted.push(i);
      countArr[i]--;
    }
  }
  return sorted;
}

---

기수 정렬

'데이터를 구성하는 기본 요소, 즉 기수를 이용해서 정렬을 진행하는 방식' 이다. 기수 정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다.

기수 정렬의 가장 큰 특징은 정렬을 위한 비교연산을 하지 않는다는 것이다.

시간 복잡도는 O(dn)이다.
같은 두 수가 있어도 순서가 섞이지 않는 안정 정렬이다

// 양의 정수만 정렬 가능한 로직
function radixSort(arr) {
  const max = Math.max(arr);
  let radix = 1; // 자릿값
  while (parseInt(max / radix) > 0) { // 최댓값이 가지는 자릿수까지만 반복
    arr = countingSort(arr, radix); // radix를 지정해서 인자로 받는 countingSort 함수를 내부적으로 이용
    raidx *= 10;
  }
  return arr;
};