[알고리즘] 2. 카운팅 정렬

1. 카운팅 정렬 Counting Sort

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 해, 선형 시간에 정렬하는 효율적인 방식
• 정수/정수로 표현 가능한 자료에 대해서만 적용 가능 → 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문!
• 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 함
• 시간 복잡도 : O(n+k)

  def counting_sort(Data, Temp, k):
  
  counts = [0] * (k+1)
  
  for i in range(len(Data)): 
  	counts[Data[i]] += 1
  
  for i in range(1,k+1):
  count[i] += counts[i-1]
  
  for i in range(len(Data)-1, -1, -1):
  counts[Data[i]] -= 1
  Temp[counts[Data[i]]] = Data[i]
  ​