계수 정렬

계수 정렬(count sort)

• 값들을 비교하지 않기 때문에 O(k+n)시간 안에 수행됨.
• 숫자에 대해서만 동작하면 특정 범위가 주어져야 함.
• 항목들을 교환하면서 정렬하는 대신에 배열의 각 항목의 등장 횟수를 셈.
• 각 항목의 등장 횟수를 센 다음 해당 등장 횟수를 사용해 새로운 배열을 생성할 수 있음.
• 계수 정렬은 항목들을 교환하지 않고도 자료를 정렬함.

코드 구현

const countSort = array => {
  let hash = {}, countArr = [];
  
  for(let i=0; i<array.length; i++) {
    if(!hash[array[i]]) hash[array[i]] = 1;
    else hash[array[i]]++;
  }
  
  for(let key in hash) {
    for(let i=0; i<hash[key]; i++) {
      countArr.push(parseInt(key));
    }
  }
  return countArr;
}

countSort([6,1,23,2,3,2,1,2,2,3,3,1,123,123,4,2,3]);