[JS] Counting Sort 구현하기

1. 계수정렬(Counting Sort)

• 각 원소들의 갯수를 체크하여 작은 순서대로 정렬

• 장점
  중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠름
  최대, 최소 값 차이가 100만 이하일 경우 효과적

• 단점
  데이터가 양의 정수일 경우만 정렬 가능
  많은 메모리 공간 필요

성능

• Best Case : $O(n)$
• Worst Case: $O(n)$
• Average Case : $O(n)$

구현코드

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]--;
		}
	}
}