계수 정렬(Counting Sort) 이란

계수 정렬

특정한 조건이 부합할 때, 배열 원소 간 비교하지 않고 정렬하는 알고리즘이다.

특정한 조건이란, 원소들이 정수이며 0~K(K=정수)의 범위 안에 포함될 때를 가정한다.

 

즉, 데이터 개수가 N개이며, 모두 0이상의 정수이며 데이터 중 최댓값이 K일 때 사용할 수 있다.

 

계수 정렬은, 각각 데이터가 몇 번 씩 등장했는지를 세는 방식이다.

 

그래서 가장 큰 데이터의 크기로 배열을 선언해서 0부터 K까지 모든 범위를 포함할 수 있어야 하며,
배열 인덱스를 이용하기 때문에 0이상의 정수를 데이터로 갖는 배열을 가정해준다.

 

계수 정렬을 수행하는 순서를 살펴보자.

 

1. 인덱스 K를 참조할 수 있는 K+1 크기의 배열 countArr을 선언하고 모든 인덱스의 값을 0으로 초기화한다.
2. 원본 배열의 첫번째 인덱스부터 순회하면서, 원본 배열의 데이터와 동일한 countArr 배열의 인덱스의 값을 1씩 증가시킨다.
      ex) 예를 들어 원본 배열의 2번째 인덱스 값이 3이라면, countArr[3]++; 을 수행한다.
3. 원본 배열의 마지막 인덱스까지 순회하고 나면, countArr 배열에는 원본 배열의 등장 횟수가 담긴다.
4. countArr 배열의 인덱스를 순회하면서, 인덱스의 값이 0이 될 때 까지 출력해준다.

 

gif를 통해 이해해보자.

출처 :  https://www.geeksforgeeks.org/counting-sort-visualization-using-javascript/

 

 

JS 코드로 작성해보았다.

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

function countingSort(arr){
	const max = Math.max(...arr);
	const len = arr.length;
	const indexArr = Array.from({length:max + 1}, ()=>0);

	for(let i=0; i<len; i++){
		indexArr[arr[i]]++;
	}
	
	let idx = 0;
	for(let i=0; i<=max; i++){
		while(indexArr[i] > 0){
			arr[idx++] = i;
			indexArr[i]--;
		}
	}
}

countingSort(arr);
console.log(arr);

배열에서 최댓값을 찾고, 최댓값+1의 크기로 배열을 선언한다.

arr 배열을 조회하며, 값에 해당하는 indexArr 인덱스의 값을 1씩 증가시킨다.

indexArr 배열을 조회하며, 각 인덱스의 값이 0이 될 때 까지 arr 배열에 순차적으로 현재 인덱스 값을 넣어준다.

 

그 결과 [4, 4, 3, 5, 1, 2, 0, 8, 3, 6] 배열이 [0, 1, 2, 3, 3, 4, 4, 5, 6, 8] 배열로 정렬된다.

---

계수 정렬의 복잡도

계수 정렬은 시간복잡도, 공간복잡도가 모두 O(N+K)이다.

 

계수를 기록하고 풀어주는 반복문을 각각 수행하므로, 전체 소스코드의 시간복잡도가 O(N+K)이다.

공간복잡도 역시 정렬을 수행할 데이터 개수 N개, 최댓값 K까지 공간이 필요하므로, N+K이다.

 

장점

알고리즘에서 데이터 간 비교를 수행하지 않기 때문에 O(N)의 시간 복잡도의 성능을 보여준다.

• 이는, 기존에 우수한 정렬 알고리즘으로 평가받는 퀵 정렬, 병합 정렬 O(NlogN) 보다 더 빠르다.

데이터가 정수 표현이 가능하고, 데이터 간 차이가 크지 않을 때 유리하다.

 

단점

많은 메모리 공간을 필요로 한다.(K 크기의 배열을 만들어야 한다.)

• ex) 데이터가 5개 존재하는데 각각 0, 3, 2, 1, 1000000 이라면?