카운팅정렬

• 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하며 선형 시간에 정렬하는 효율적인 알고리즘
• 제한사항
  • 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능 : 각 항목의 발생 회수를 기록하기 위해 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
  • 카운트들을 위한 충분한 공간을 할당하려면 집합 내 가장 큰 정수를 알아야한다.
• 시간 복잡도 : O(n+k) :n은 리스트의 길이, k는 정수 최대값
• 1단계 : Data에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열 counts에 저장
• 2단계 정렬된 집합에서 각 항목의 앞에 위치할 항목의 개수를 반영하기 위해 원소를 조정
• counts[i]를 감소시키고 temp에 삽입

def counting_sort(input_arr, k):
    # k : 0 ~ k

    # 원소들의 개수를 셀 빈 리스트를 만들어줍니다. 개수가 없을수도 있으니 0으로 초기화를 해줍니다.
    counting_arr = [0] * (k + 1)

    # 전체 리스트를 돌면서 개수를 세어줍니다.
    for i in range(len(input_arr)):
        counting_arr[input_arr[i]] += 1
    # 개수가 들어있는 counting array를 input_array의 원소들의 인덱스를 바라볼 수 있도록 변경해줍니다.
    for i in range(1, len(counting_arr)):
        counting_arr[i] += counting_arr[i - 1]

    # 결과가 담길 리스트를 초기화해줍니다. 0~k가 아닌 값으로 초기화해주는게 오류를 확인하기 좋습니다
    result_arr = [-1] * len(input_arr)

    # 오른쪽 -> 왼쪽의 흐름을 왼쪽 -> 오른쪽 흐름으로 가져오기 위해 리스트를 뒤집어줍니다.
    input_arr = input_arr[::-1]
    # input_arr의 값을 index로 가져옵니다. 이를 사용하여 counting_arr에 들어있는 해당 값이 들어갈 수 있는 가장 오른쪽 index를 찾습니다.
    # counting_arr의 숫자는 1부터 시작하는 "번째"의 개념이고, 파이썬은 0부터 시작하기 때문에 -1을 하여 값을 맞추어줍니다.
    # -1을 한 값에 맨 처음 가져온 input_arr의 값을 넣어줍니다.
    for i in input_arr:
        counting_arr[i] -= 1
        result_arr[counting_arr[i]] = i

    return result_arr

lst = [0, 4, 1, 3, 1, 2, 4, 1]

print(counting_sort(lst, 5)) # [0, 1, 1, 1, 2, 3, 4, 4]

1. 주어진 숫자의 범위만큼 카운팅배열을 만들어준다.
2. 전체 리스트를 돌면서 각 숫자의 개수를 세준다.
3. 개수가 들어있는 카운팅 리스트가 순서를 가지도록 각 값에 이전 개수를 더해준다.
   • 예를들어 131120이면
   • 145688
4. 결과를 담을 배열을 각 값을 -1로 지정한 후 만들어준다.
5. 흐름을 변경하기 위해 input_arr을 뒤집어준다 (input_arr[::-1])
6. input_arr의 값을 index로 counting_arr에 들어있는 값을 -1한 후 (counting_arr[i])번째로 result_arr에 추가해줌