계수 정렬(Counting Sort)

계수 정렬은 범위 조건이 있는 경우에 한해서 빠른 알고리즘이다.

조건이 충족되면 O(n)의 시간 복잡도를 갖는다.

1. 계수 정렬(Counting Sort) 문제

1 3 2 4 3 2 5 3 1 2 3 4 4 3 5 1 2 3 5 2 3 1 4 3 5 1 2 2 1 1

위의 숫자 데이터를 오름차순으로 정렬하라

2. 계수 정렬(Counting Sort) 문제 풀이

위의 문제를 보게되면 1에서 5까지 범위가 정해져 있는 것을 볼 수 있다.

위의 문제는 데이터의 크기를 기준으로 센 뒤에 갯수만큼 나열하면 해결되는 문제이다.

각 요소마다 크기를 세어 주면 되므로 O(n)을 갖는다.

const arr = [
	1, 3, 2, 4, 3, 2, 5, 3, 1, 2, 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 3, 1, 4, 3, 5,
	1, 2, 2, 1, 1,
];

function countingSort(arr) {
	// 정렬된 데이터를 담을 배열
	const result = [];

	// 범위의 크기만큼 배열을 만들어준다
	const count = new Array(5).fill(0);

	// 데이터의 요소의 크기에 따라 해당하는 인덱스를 증가시킨다.
	for (let i = 0; i <= arr.length - 1; i++) {
		count[arr[i] - 1]++;
	}

	for (let i = 0; i <= count.length - 1; i++) {
		if (count[i] !== 0) {
			for (let j = 0; j <= count[i] - 1; j++) {
				result.push(i + 1);
			}
		}
	}

	return result;
}

const sorted = countingSort(arr);

console.log(sorted);

// [
//   1, 1, 1, 1, 1, 1, 1, 2, 2,
//   2, 2, 2, 2, 2, 3, 3, 3, 3,
//   3, 3, 3, 3, 4, 4, 4, 4, 5,
//   5, 5, 5
//]

3. 계수 정렬(counting sort)의 한계점

계수 정렬은 한정된 범위의 크기에 따라서 효율이 달라진다.

[ 1, 1, 2, 3, 4, 5, 1, 1, 3, 4, 10000000]

1 ~ 10000000의 범위를 갖는 데이터

만약 위와 같이 데이터가 있다면 범위가 1에서 10000000 까지 이므로 데이터 갯수에 비해 많은양의 연산이 들어간다.

이런 경우에는 계수 정렬이 아닌 다른 알고리즘을 적용하는 것이 바람직하다.