ZeroCho Blog

안녕하세요! 이번 시간에는 계수 정렬에 대해 알아보겠습니다.

계수 정렬은 놀랍게도 작은 숫자에서는 복잡도가 O(n + k)입니다. n+k는 처음 보죠? k가 정렬할 수들 중에 가장 큰 값을 의미하는데요. 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있습니다. 예를 들어 10개의 숫자를 정렬하는 데, 가장 큰 숫자가 100일 경우, O(n^2)이 됩니다. 100(k)은 10(n)의 제곱이니까요. 1000이면 O(n^3)이 되죠. 즉 정렬할 수들의 최대값에 영향을 받는 알고리즘이라고 볼 수 있습니다.

방법은 매우 간단합니다. 모든 숫자의 개수를 센 후, 누적 합을 구하고, 다시 숫자를 넣어주면 됩니다.

[3,4,0,1,2,4,2,4], [개수를 저장할 공간], [결과]
개수를 저장할 공간을 정렬할 제일 큰 수의 갯수만큼 0으로 만들어줍니다.
[3,4,0,1,2,4,2,4], [0,0,0,0,0], [결과]
처음부터 개수를 세어 저장합니다. 0은 1개, 1은 1개, 2는 2개, 3은 1개, 4는 3개네요.
[3,4,0,1,2,4,2,4], [1,1,2,1,3], [결과]
개수를 저장한 것을 누적합으로 바꿔줍니다. 순서대로 1, 2, 4, 5, 8이 됩니다.
[3,4,0,1,2,4,2,4], [1,2,4,5,8], [결과]
누적합을 바탕으로 숫자를 결과에 넣어줍니다. 0은 1에, 1은 2에, 2는 3~4에 3은 5에, 4는 6~8에 넣어주면 됩니다.
[3,4,0,1,2,4,2,4], [1,2,4,5,8], [0,1,2,2,3,4,4,4]

정말 간단하죠? 누적합이 바로 숫자들의 인덱스 역할을 합니다. 1,3,4,7이 있으면 1은 0~1 사이에, 2는 1~3 사이에, 3은 3~4 사이에, 4는 4~7 사이에 넣으라는 뜻입니다. 코드로 볼까요?

var countingSort = function(array, k) {
  var count = [], result = [];
  for (var i = 0; i <= k; i++) { // 모든 숫자의 개수를 일단 0으로 초기화합니다.
    count[i] = 0;
  }
  console.log(count, result, array.length);
  for (var j = 0; j < array.length; j++) { // 숫자의 개수를 세어 저장합니다.
    count[array[j]] += 1;
  }
  console.log(count, result, k);
  for (i = 0; i < k ; i++) { // 누적합을 구합니다.
    count[i + 1] += count[i];
  }
  console.log(count, result);
  for (j = 0; j < array.length; j++) { // 누적합이 가리키는 인덱스를 바탕으로 결과에 숫자를  집어넣습니다.
    console.log(array[j], count[array[j]] - 1);
    result[count[array[j]] - 1] = array[j];
    count[array[j]] -= 1;
  }
  console.log(count, result);
  return result;
};

// 배열에 큰 수가 들어갈 수록 메모리를 많이 잡아먹기 때문에 좋지 않습니다.
countingSort([3,4,0,1,2,4,2,4], 4); // [0,1,2,2,3,4,4,4]

계수 정렬은 우리가 배운 알고리즘 중에 처음으로 비교 정렬이 아닙니다. 이전까지는 두 수를 비교하여 정렬했다면 이 방법은 단 하나의 비교도 일어나지 않았습니다. 그리고 같은 숫자라도 정렬할 때 순서가 섞이지 않는 안정 정렬입니다.

단, 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점입니다. 그래도 적은 개수의 숫자를 정렬할 때는 계수 정렬을 사용하세요.

다음 시간에는 기수 정렬에 대해 알아보겠습니다!