안녕하세요! 이번 시간에는 계수 정렬에 대해 알아보겠습니다.
계수 정렬은 놀랍게도 작은 숫자에서는 복잡도가 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]계수 정렬은 우리가 배운 알고리즘 중에 처음으로 비교 정렬이 아닙니다. 이전까지는 두 수를 비교하여 정렬했다면 이 방법은 단 하나의 비교도 일어나지 않았습니다. 그리고 같은 숫자라도 정렬할 때 순서가 섞이지 않는 안정 정렬입니다.
단, 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간, 결과를 저장할 공간)가 필요하다는 점과, 가장 큰 숫자에 영향을 받는다는 점은 단점입니다. 그래도 적은 개수의 숫자를 정렬할 때는 계수 정렬을 사용하세요.
다음 시간에는 기수 정렬에 대해 알아보겠습니다!
이번 정렬알고리즘은 400,401,404같이 각각의 최대값은 큰데 값의 범위는 작은 배열의 경우
최소값도 따로 구해서 카운팅배열의 크기를 최대값에서 최소값을 뺀만큼의 숫자로 만들어도 좋을 것 같네요