Counting Sort (카운팅 정렬)

Counting sort란?

알고리즘을 공부하면서 선택정렬, 버블정렬, 퀵 정렬 등 다양한 정렬을 들어봤지만 이상하게 카운팅 정렬 즉 계수 정렬은 생소했습니다.

카운팅 정렬이란 항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘입니다.

보통 정렬할 값이 양의 정수이고, 자료의 범위를 알고 있을 때 사용한다고 합니다.

제한사항!

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

구현

def Counting_Sort(A,B,k):
    C = [0]*(k+1)       # Counting Array (0부터 최댓값 k까지 이므로 k+1개)

    for i in range(0,len(B)):       # 0 ~ A나 B Array의 길이 만큼 반복
        C[A[i]]+=1                  # A의 Array 요소 개수 C에 담기

    for i in range(1, len(C)):      # C에 각 요소 누적 합 담기
        C[i] += C[i-1]

    for i in range(len(A)-1, -1, -1):       # A의 원소 값을 역순으로 담기 위해서
        B[C[A[i]]-1] = A[i]                 # B의 (A 원소 값의 C의 인덱스 - 1) =(C[A[i]) 위치에 값을 넣어준다
        C[A[i]] -= 1                        #  그 후 C 누적 값의 값을 빼준다 왜냐? B에 넣어줬으니깐!
    return B

# A  []  -- 입력 배열 (1 to k)
# B  []  -- 정렬된 배열 담을 그릇.
# C  []  -- 카운트 배열 + 누적 값.
A = [0,1,4,2,3,3,0]
B = [-1]*len(A)				#B는 -1로 전부 초기화
k = 4
print(Counting_Sort(A,B,k))		#[0, 0, 1, 2, 3, 3, 4]

Counting Sort의 시간 복잡도

Counting Sort의 시간 복잡도는 O(n+k)입니다.
이때 n은 정렬할 리스트의 길이이고, k는 리스트의 정수 최댓값을 의미합니다.

데이터 개수가 n일 때 시간 복잡도는 O(n)입니다. 정렬된 배열을 담을 B를 만들 때도 O(n)이다. =>(A의 요소를 역순으로 훑기 때문)

또한 C의 크기가 충분히 작을 때는 O(n)의 복잡도를 가지겠지만, k가 커질 경우 O(n+k)의 복잡도를 가집니다. (즉 최댓값이 클수록 시간 복잡도가 커짐)

유명하신 ratsgo님의 블로그(여기)를 참고하였습니다.