계수 정렬

☝ 계수 정렬은 값의 크기를 비교하는 다른 정렬과 달리, 중복 된 데이터의 값을 세어주는 방법을 이용하기 때문에 중복 된 값이 많은 데이터를 정렬할 때 유용하다.

🎫 개념

우선 중복된 값의 개수를 세어준다. 그 다음 중복된 값의 개수들을 누적해서 다른 배열에 저장해준다. 마지막으로 값의 개수들이 저장된 배열을 차례대로 누적된 개수만큼 출력한다.

🤔 모든 수에 가능할까?

양의 정수에 대해서만 적용이 가능하다.

❓ 예시

arr = [0,1,3,3,2,4,5,5,1,1,3]
0이 1개, 1이 3개, 2가 1개, 3이 3개, 4가 1개, 5가 2개 이므로,

count[idx]+=1을 통해
count[0,0,0,0,0] -> [1,3,1,3,1,2]가 된다.

배열에 저장된 값 만큼 해당 idx를 반복해서 출력해주면
[0,1,1,1,2,3,3,3,4,5,5]

💻 코드 구현 (python)

def counting_sort(arr):
    n = max(arr)+1
    cnt = [0]*n
    sorted = []

    #중복된 값의 개수를 해당 idx에 저장
    for i in arr:
        cnt[i] += 1

    #중복된 만큼 차례대로 idx 출력
    for i in range(n):
        for j in range(cnt[i]):
            sorted.append(i)

    return sorted

if __name__ == '__main__' :
    arr = list(map(int, input().split()))
    print(counting_sort(arr))

⏰ 시간 복잡도

계수 정렬은 비교를 하지 않기 때문에 시간 복잡도는 O(n)이다.
무척 빠르지만, 정렬하고자 하는 데이터 중 가장 큰 값에 해당하는 길이만큼 메모리를 할당해야 해서 메모리 낭비가 심하기 때문에 특정 범위 안의 숫자가 분포되어 있을 때 써야 한다.