- 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다.
- 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다.
- 계수 정렬은 시간 복잡도가 **O(n + k)**이다.
- 데이터의 개수 n, 데이터 중 최대값의 크기 k이다.
- 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다.
동작 과정
[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]
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); // [ 0, 0, 0, 0, 0 ] [] 8
for (var j = 0; j < array.length; j++) {
// 숫자의 개수를 세어 저장합니다.
count[array[j]] += 1;
}
console.log(count, result, k); // [ 1, 1, 2, 1, 3 ] [] 4
for (i = 0; i < k; i++) {
// 누적합을 구합니다.
count[i + 1] += count[i];
}
console.log(count, result); // [ 1, 2, 4, 5, 8 ] []
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);
// 3 4
// 4 7
// 0 0
// 1 1
// 2 3
// 4 6
// 2 2
// 4 5
return result; // [0, 1, 2, 4, 5][(0, 1, 2, 2, 3, 4, 4, 4)];
};
// 배열에 큰 수가 들어갈 수록 메모리를 많이 잡아먹기 때문에 좋지 않습니다.
countingSort([3, 4, 0, 1, 2, 4, 2, 4], 4); // [0,1,2,2,3,4,4,4]