[알고리즘] 특수 정렬 알고리즘

기수 정렬 알고리즘

• 모두 k 자릿수 이하의 자연수인 특수한 경우
• 시간 복잡도
  • O(n)

계수 정렬 알고리즘

• 정렬하고자 하는 원소들의 값이 O(n)을 넘지 않는 경우
• 정렬할 데이터에 대한 사전 지식을 이용
• 시간 복잡도
  • O(n)

arr = [1,2,5,4,7,8]
count = [0] * (max(arr) + 1)
for num in arr:
    count[num] += 1

for i in range(1, len(count)):
    count[i] += count[i-1]

result = [0] * (len(arr))

for num in arr:
    idx = count[num]    
    result[idx - 1] = num    
    count[num] -= 1

print(result)