계수 정렬(Counting Sort)
계수 정렬 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
데이터의 개수가 N, 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 O(N + K)의 시간 복잡도를 보장하므로 빠른 정렬 알고리즘으로 유명한 퀵 정렬의 시간복잡도인 O(NlogN) 보다 빠른 속도를 보장한다.
이러한 빠른 속도를 보장하는데 왜 계수 정렬만을 사용하지 않을까요 ? 이는 계수 정렬의 동작원리를 살펴보고 아래의 정리 부분에서 다루겠습니다.
동작 원리
-
보통 정수의 0 부터 데이터 집합에서 가장 큰 데이터를 인덱스로 가질 수 있는 크기의 배열을 선언하고 0으로 초기화한다.
-
기존 데이터 집합에 포함된 요소들을 초기화 된 배열의 인덱스로 접근하여 카운팅을 합니다.
-
2의 단계를 거치면 데이터 집합의 요소에 해당하는 값들이 새로 생성한 카운팅 배열에 몇 번 나왔는지 확인할 수 있는 배열이 생성됩니다.
-
3의 생성된 배열을 토대로 0부터 가장 큰 값의 인덱스까지 카운팅 된 횟수만큼 인덱스를 출력하면 정렬된 데이터 형태가 됩니다.
동작원리를 토대로 아래의 그림 처럼 정렬되지 않은 배열을 정렬해봅시다.
범위가 0~5인 배열임을 파악하고 카운팅하는 배열을 선언 및 초기화합니다.
인덱스 순으로 count[0]은 1의 개수를, count[1]은 2의 개수를 의미로 접근하여 개수를 카운팅합니다. 다만 count[0]은 0의 개수를 의미하게 접근하도록 배열의 크기를 +1 하여 선언하여도 좋은 접근법입니다.
입력 배열을 순차적으로 탐색하여 카운팅을 마칩니다.
그 후 카운팅 배열의 각 원소의 값만큼 인덱스를 출력하면 정렬된 형태를 볼 수 있습니다.
구현
const countingSort = (array) => {
const maxValue = Math.max(...array);
const countedArray = new Array(maxValue + 1).fill(0);
const sortedArray = [];
for (let i = 0; i < array.length; i++) {
countedArray[array[i]]++;
}
for (let i = 0; i < countedArray.length; i++) {
for (let j = 0; j < countedArray[i]; j++) {
sortedArray.push(i);
}
}
return sortedArray;
};
const array = [5, 4, 3, 2, 1, 1, 1, 1, 3, 4, 5, 5, 2, 2, 2];
console.log(countingSort(array));
정리
살펴본바와 같이 계수 정렬은 퀵 정렬 보다 시간복잡도면에서 훨씬 유리해 보이지만, 계수정렬의 경우 대부분의 상황에서 엄청난 메모리 낭비를 초래할 수 있습니다.
데이터 집합에서 가장 작은 데이터와 가장 큰 데이터의 차이가 광범위 하다면 그 광범위 만큼에 해당하는 크기의 배열들이 메모리 공간에 필요하기 때문입니다.
따라서 정렬을 하고자 하는 데이터의 특성을 파악하기 쉽고 가장 작은 데이터와 가장 큰 데이터의 범위 차이가 1,000,000을 넘지 않는다면 일반적으로 계수 정렬이 퀵 정렬 보다 유리합니다.
하지만 데이터의 특성을 파악하기 힘들고 데이터의 범위가 광범위한 경우 우리는 평균적으로 빠르게 동작하는 퀵 정렬을 사용하는 것이 유리할 것 입니다.
다시 말해 계수 정렬은 데이터의 크기가 한정, 데이터가 많이 중복되어 있는 경우에 유리하며 항상 사용할 수 없다. 그만큼 조건만 만족한다면 계수 정렬은 정렬해야 하는 데이터의 개수가 매우 많을 때에도 효과적인 성능을 보장할 수 있다라고 정리할 수 있습니다.
참고자료
