7.계수 정렬 (Counting sort)

사전 조건

- 배열의 인자 값의 범위가 작을 때 적합하다.

동작 방식

- 배열의 인자를 하나씩 꺼낸 인자값과 새로운 배열의 인덱스 값이 같은 새로운 배열의 인자값을 1식 증가시켜준다.

장점

- 배열의 인자 값의 범위가 적을 경우 매우 빠른 속도를 낼 수 있다.
- 그러나 배열의 크기가 작고 인자값의 크기가 큰 경우 부적합 할 수 있다.

시간 복잡도

O(n) - 최대 값이 주어졌다면
    - 배열의 인자 값의 갯수 만큼 업데이트 하기 때문에 O(n)
    - 새로운 배열의 인자값들의 개수(k)를 합해야 하기 때문에 O(k)
    - 원소들을 새로운 배열에 넣어야 하기 때문에 O(n)
    - 따라서 O(2n + k) 간단하게 O(2n + k)
    - 그러나 k값 즉 인자의 최대 값이 작다면 O(n)으로 표현 할 수 있다.

python 구현

    '''
    @ Author : bsh0817
    @ Created : 2020. 01. 28
    @ Update : 2020. 01. 28
    @ Description : Counting sort (계수 정렬)
    '''


    def fn_counting_sort(list_input, int_max_value):
        '''
            @Description: Counting sort (계수 정렬)

            @Arguments Example
                # 0~10 사이의 정수라 가정
                list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
        '''
        list_result = [0] * (int_max_value + 1)
        responce = []
        for int_value in list_input:
            list_result[int_value] += 1

        for int_index in range(int_max_value + 1):
            for _ in range(list_result[int_index]):
                responce.append(int_index)
        return responce


    if __name__ == "__main__":
        list_fn_counting_sort_param = [1, 9, 1, 2, 7, 3, 2, 8, 6, 1, 10, 10, 5, 6, 5, 9]
        print(fn_counting_sort(list_fn_counting_sort_param, 10))