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

 

 

 

🧐 Non-Comparison Sort

이전 글에서 Comparison Based Sort는 Lower Bound가 Ω(n log n)이라는 것을 살펴보았습니다.

 

이번에 살펴볼 알고리즘은 시간 복잡도가 O(n)인 정렬 알고리즘입니다.

이는 Comparison Based Sort가 아니기 때문에 이전에 구한 Lower Bound는 잘못되지 않았음을 미리 밝히고 넘어가겠습니다.

 

 

 

 

 

 

 

 

 

🧐 Counting Sort (계수 정렬)

우선 배열 A[0, ..., n]를 1부터 k 사이의 정수 배열이라 하겠습니다.

 

계수 정렬은 다음과 같이 이루어집니다.

크기가 k인 Counter 배열 C[0, 1, 2, ..., k]를 정의합니다.
해당 값들을 모두 0으로 초기화합니다.

A[0]부터 A[n]까지 읽으면서 $0 \leq i \leq n$ 에 대하여 C[A[i]]의 값을 1 증가시켜줍니다.

C[0]부터 C[k]까지 왼쪽에서 오른쪽으로 읽으면서 $1 < i \leq k$ 에 대하여 C[i] = C[i] + C[i-1]로 수정해 줍니다.
위 과정을 통해 C[i]는 i보다 작거나 같은 원소의 개수가 저장됩니다.

임시 배열 B를 생성한 이후 A를 오른쪽에서 왼쪽으로 읽으면서 $1 \leq j \leq n$ 에 대하여 A[j]를 B[C[A[j]]]에 넣어 주고, C[A[j]]의 값을 1 낮춰줍니다.

위 과정이 끝나면 B가 정렬된 배열이 됩니다.

 

 

 

 

예를 들어 길이가 8이고 최댓값이 6인 배열 A에 대하여 계수 정렬을 진행해 보겠습니다.

 

배열 A는 다음과 같습니다.

 

 

이를 통해 배열 C를 생성해 보겠습니다.

 

 

 

이제 해당 C에 대해서 왼쪽에서 오른쪽으로 읽어가며 C를 업데이트 해주겠습니다.

 

 

 

 

임시 배열 B를 만들고, A의 오른쪽부터 왼쪽으로 읽어가며 B를 채우겠습니다.

 

 

 

 

해당 과정을 반복하면, 최종 결과는 다음과 같습니다.

 

 

 

 

 

 

 

🧐 수도 코드

 

 

 

 

 

🧐 시간 복잡도

n은 배열의 길이이며, k는 배열의 최댓값을 의미합니다.

총 4번의 최대 크기가 max(n, k)인 linear loop를 수행하므로, O(n+k) 입니다.

따라서 k = O(n) 이라는 가정 하에서 총 수행 시간은 O(n)이 됩니다.