[algorithms] 계수 정렬 (count sort)

(23.05.14)

https://github.com/gompaang/algorithm_python

GitHub - gompaang/algorithm_python

---

Count sort (계수 정렬)

모든 데이터가 양의 정수이고, 데이터의 범위가 제한 적일 경우에 사용하면 매우 빠르다.

시간 복잡도와 공간 복잡도는 O(N+K) 이다.

동일한 값을 가지는 데이터가 여러 개 등장할 때 사용하기에 적합하다.

 

# count sort

def count_sort(array):
  count = [0] * (max(array)+1)
  result = []
  
  for i in array:
    count[i] += 1
  
  for i in range(len(count)):
    for j in range(count[i]):
      result.append(i)
  
  return result

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
print(count_sort(array))

 

 

 

 

 

 

참고자료: 이것이 코딩 테스트다 (나동빈)

https://github.com/ndb796/python-for-coding-test