계수 정렬 (Counting Sort)알고리즘 동작 과정

계수 정렬은 원소의 빈도수를 기준으로 정렬하는 알고리즘입니다
실제 데이터 예시를 통해 계수정렬 알고리즘의 동작과정을 살펴보겠습니다

다음과 같은 숫자 배열을 오름차순으로 정렬하겠습니다
[4, 2, 2, 8, 3, 3, 1]

1회차 동작과정

배열의 데이터 중 최댓값을 찾아 계수 배열의 크기를 정합니다
예시 배열의 최댓값은 8이므로 0~8까지의 9크기의 공간을 가집니다
[0, 0, 0, 0, 0, 0, 0, 0, 0]

2회차 동작과정

주어진 원본 배열을 확인하며, 원소의 빈도수를 계수 배열에 기록합니다
결과적으로 다음과 같은 계수 배열을 얻습니다
[0, 1, 2, 2, 1, 0, 0, 0, 1]

3회차 동작과정

계수배열에 누적합을 적용합니다
[0, 1, 3, 5, 6, 6, 6, 6, 7]

4회차 동작과정

초기 원본 배열의 데이터를 뒤에서부터 탐색합니다
그리고 누적된 계수배열을 참고하여, 정렬된 위치에 값을 배치합니다
참고할 때마다 계수값을 1씩 감소시킵니다

결과적으로 다음과 같은 오름차순 정렬된 배열을 얻습니다
[1, 2, 2, 3, 3, 4, 8]

정리

계수 정렬(Counting Sort)알고리즘은 원소의 빈도수를 기준으로 정렬하는 알고리즘입니다
원소의 빈도수를 기반으로 원소간 비교 없이 정렬할 수 있는 정렬 알고리즘입니다