[자료구조] 계수 정렬(counting sort)

카운팅 정렬은 특정 문제 상황이 발생했을 때 효율이 굉장히 좋아진다. 간단한 예로 영어로 된 소설 하나를 알파벳순으로 정렬한 배열을 얻고 싶다할 때

사용할 수 있다.

계수 정렬(counting sort)

데이터셋은 다음과 같다. [ 1, 3, 4, 4, 1, 4, 3, 4, 0 ]

1. 위 데이터셋은 1 ~ 5까지의 값 중 하나다.
2. 가질 수 있는 값의 최대 값을 크기로 하는 배열C를 만든다. (여기서는 5가 최고값이므로 크기가 5인 배열을 준비한다.)
3. 나온 값의 갯수를 카운팅한다. C = [ 1, 2, 0, 2, 4 ] (0은 1개, 1은 2개, 2는 0개, 3는 2개 4는 4개)
4. 2에서 처럼 최대값을 크기로 하는 배열A를 만든다. 배열 A에는 누적합을 넣는다.
5. 누적합을 구한다. A = [1, 3, 3, 5, 9]  A[k] = A[k-1] + C[k]  k = 0 ~ 4, A[-1] = 0
6. 우선 정렬된 배열을 저장하기 위해 결과값을 저장한 배열 R을 만든다. [-1, -1, -1, -1, -1, -1, -1, -1, -1]
7. 원래 데이터 셋의 끝부터 숫자 하나씩 꺼낸다. 여기선 0.
8. 0의 누적합의 값은 1인데, 값을 1 마이너스 시키면 0. A[0]에는 0을 대입한다.
9. 0을 0인덱스에 넣는다.  [0, -1, -1, -1, -1, -1, -1, -1, -1]
10. 데이터셋에서 다음 끝 숫자를 꺼낸다. 여기선 4.
11. 4의 누적합의 값은 9인데 9에서 1을 뺀 값은 8. A[4] 에는 8을 대입한다.
12. 4를 8인덱스에 넣는다. [0, -1, -1, -1, -1, -1, -1, -1, 4]
13. 데이터셋 끝에서 부터 값을 꺼내 위 과정을 반복한다.

글로 설명하면 조금 헷갈릴 수 있다.

코드로 보면,

	const input = [3, 4, 3, 5, 4, 1, 4, 5, 1, 4, 4, 3, 1, 1];
	let d = [...input];
	const counting = function(arr) {
	let countingArray = [];
	for(let item of arr) {
	countingArray[item] = countingArray[item] ? countingArray[item] + 1 : 1;
	}
	return countingArray;
	}
	const accumulate = function(arr) {
	let accumulatingArray = [];
	let accumulateSum = 0;
	arr.forEach((value, index) => {
	accumulateSum = value ? accumulateSum + value : accumulateSum;
	accumulatingArray[index] = accumulateSum;
	});
	return accumulatingArray;
	}
	const countingSort = function(arr, accumulatingArray) {
	let sortedArray = [];
	let value, accumulateSum;
	for (let idx = arr.length - 1; idx > -1; idx--) {
	value = arr[idx];
	accumulateSum = accumulatingArray[value];
	if(accumulateSum) {
	accumulatingArray[value] = --accumulateSum;
	sortedArray[accumulateSum] = value;
	}
	}
	return sortedArray;
	}
	const countingArray = counting(d);
	let accumulatingArray = accumulate(countingArray);
	console.log(countingSort(d, accumulatingArray));

view raw countingSort.js hosted with ❤ by GitHub

내 기억에 계수 정렬을 면접 문제에서도 심심찮게 나왔던 것 같다. 기억하자, 정렬할 값의 범위가 한정적일 때 (위 예시처럼 소설을 몇만자 이지만, 가질 수 있는 값이 대문자 소문자 알파벳이라고 하면) 매우 좋은 효율을 갖는다.

다음은 기수 정렬 또는 힙 정렬로 찾아뵙겠습니다.