[알고리즘] 계수 정렬에 관하여

• 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
• 계수 정렬은 ‘데이터 크기 범위가 제한 되어 정수 형태로 표현할 수 있을 때’만 사용할 수 있다.
• 무한한 범위를 가질 수 있는 실수형 데이터가 주어지는 경우는 사용하기 어렵다.
• 일반적으로 가장 큰 데이터와 가장 작은 데이터 차이가 1,000,000을 넘지 않을 때 효과적으로 사용할 수 있다. (그 이후는 리스트를 초기화 해야 하기 때문)

function countSort(array) {
  let ans = [];
  let count = Array(Math.max(...array) + 1).fill(0);

  for (let i = 0; i < array.length; i++) {
    count[array[i]] += 1;
  }

  for (let i = 0; i < count.length; i++) {
    for (let j = 0; j < count[i]; j++) {
      ans.push(i);
    }    
  }

  return ans;
}

 

시간 복잡도

• 계수 정렬의 시간 복잡도는 O(N + K)이다
  • 최악 - O(N + K)
  • 최고 - O(N + K)
  • N은 데이터 개수를 의미한다
  • K는 데이터중 최대값의 크기를 의미한다

참고

1. 이것이 취업을 위한 코딩 테스트다 with 파이썬, 나동빈: https://books.google.ca/books?id=vBz-DwAAQBAJ&source=gbs_book_other_versions