정렬 알고리즘 - 계수 정렬(Counting Sort)

원소들의 순서를 결정하기 위해 원소들이 몇 개씩 있는지 세어서 적절한 위치에 선형 시간에 정렬하는 알고리즘을

의미한다. 비교 기반 정렬 알고리즘과 다르게 직접 데이터의 값을 비교하지 않습니다.

1. 최초 배열 arr에 존재하는 값의 각 원소의 개수를 세어줄 새로운 배열 count를 만들어줍니다.
2. count 배열의 원소를 누적합 값으로 갱신해줍니다.
3. arr의 길이와 같은 result 배열을 만들어줍니다.
4. arr의 각 원소의 값을 count의 인덱스로 사용해 값을 가져온 후, 해당 값을 다시 result의 인덱스로
5. 사용해 arr의 값을 저장합니다.
6. count[arr[i]]의 값을 하나 줄여줍니다.
7. 위 과정을 반복합니다.

시간복잡도는 **O(n + k)**입니다. k가 충분히 작을 경우 시간복잡도가O(n)이 되겠지만,

k값이 커질 경우 k가 시간복잡도를 지배하게 됩니다. 공간복잡도는 O(k)입니다.

 

장점

• 선형 시간에 정렬이 가능하다.

단점

• 정수나, 정수로 표현할 수 있는 자료에 대해서만 적용 가능하다.
• 각 항목의 발생 횟수를 기록해야 하기 때문에 정수로 인덱스 되는 카운트들의 배열(메모리) 사용한다.
• 카운트를 위한 충분한 공간을 할당하기 위해서는 집합 내의 가장 큰 정수를 알아야한다.

def counting_sort(arr):
    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

    return result