카운팅 정렬

• 배열에 존재하는 원소의 갯수를 세고, 순서대로 그 배열을 나열하는 방식의 정렬.
• 배열의 최댓값을 $k$라 할 때 시간 복잡도는 $O(n + k)$.
• $k$가 크지 않다면 매우 효율적인 방법이다.

구현

구현에는 여러 방법이 있지만 여기서는 싸피에서 배운 걸 작성한다.

def counting_sort(arr: list) -> list:
    max_val = max(arr)
    # counting 배열 만들기
    count_arr = [0] * (max_val + 1)
    for num in arr:
        count_arr[num] += 1
    # counting 배열 누적합으로 만들기
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i - 1]
    # 정렬된 배열이 될 temp
    temp = [0] * len(arr)
    for j in range(len(arr) - 1, -1, -1):
        num = arr[j]
        count_arr[num] -= 1
        temp[count_arr[num]] = num
    return temp