계수 정렬
계수 정렬(Counting Sort)은 비교 기반 정렬 알고리즘이 아닌, 선형 시간(linear time)에 정렬을 수행하는 알고리즘입니다.
계수 정렬 장단점
장점
•
비교 기반 정렬 알고리즘보다 빠릅니다.
•
데이터의 범위가 제한되어 있는 경우, 즉 데이터의 분포가 고르게 퍼져 있는 경우 효율적입니다.
•
안정 정렬(Stable Sort)입니다.
단점
•
데이터의 범위가 크거나 데이터의 분포가 고르게 퍼져 있지 않은 경우 메모리 사용량이 매우 많아질 수 있습니다.
•
정렬에 필요한 추가적인 메모리가 필요합니다.
계수 정렬 동작 순서
1.
정렬할 배열의 값들 중 최솟값과 최댓값을 구합니다.
2.
최솟값부터 최댓값까지의 범위를 가지는 카운팅 배열(counting array)을 생성합니다.
3.
배열의 값을 읽어 카운팅 배열의 해당 인덱스에 값을 추가합니다.
4.
카운팅 배열의 값을 누적하여 누적합(cumulative sum)을 계산합니다.
5.
원본 배열의 값을 읽어, 카운팅 배열에서 누적합을 이용하여 정렬된 위치를 찾아 값을 채웁니다.
6.
원본 배열이 정렬됩니다.
