도수 정렬 Counting Sort

**도수 정렬(Counting Sort)**은 정렬할 데이터의 값의 범위를 알고 있을 때 매우 효율적인, 비교를 하지 않는(non-comparison) 정렬 알고리즘입니다. 각 숫자가 몇 번 등장하는지(도수)를 세어 정렬하는 방식입니다.

도수 정렬의 원리

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

카운팅 배열 생성: 정렬할 데이터의 최솟값부터 최댓값까지의 범위를 포함할 수 있는 카운팅 배열(Counting Array)을 만듭니다. 이 배열은 각 숫자의 등장 횟수를 기록하기 위한 용도이며, 모든 값을 0으로 초기화합니다.
도수 계산: 원래 배열을 순회하면서 각 숫자가 나올 때마다 카운팅 배열의 해당 인덱스 값을 1씩 증가시킵니다. 예를 들어, 원래 배열에서 숫자 3이 나오면 카운팅 배열의 3번째 인덱스 값을 1 증가시킵니다.
누적 합 계산: 카운팅 배열의 각 인덱스에 이전 인덱스들의 값을 더해 누적 합을 구합니다. 이렇게 하면 각 숫자가 정렬된 배열에서 어느 위치에 들어가야 하는지를 알 수 있습니다.
정렬된 배열 생성: 새로운 결과 배열을 만듭니다. 원래 배열을 뒤에서부터 순회하면서 각 숫자에 해당하는 카운팅 배열(누적 합)의 값을 보고 결과 배열의 해당 위치에 값을 채워 넣습니다. 값을 채운 뒤에는 카운팅 배열의 값을 1 감소시켜 다음 중복된 값이 올바른 위치에 들어가도록 합니다.

매우 빠름: 특정 조건 하에서 시간 복잡도가 $O(n+k)$로 매우 빠릅니다. (여기서 n은 데이터의 개수, k는 데이터의 값의 범위)
안정 정렬: 같은 값의 데이터는 원래의 순서가 유지되는 안정(Stable) 정렬입니다. 이는 다른 정렬 알고리즘의 일부로 사용될 때 중요한 특징입니다.

메모리 사용량: 데이터의 값의 범위(k)가 매우 클 경우, 카운팅 배열의 크기도 커져 메모리 낭비가 심할 수 있습니다. 예를 들어 [1, 2, 10000]과 같은 배열을 정렬하려면 10001개의 공간을 가진 배열이 필요합니다.
데이터 타입 제한: 정수와 같이 값의 범위가 명확한 데이터에만 적용할 수 있습니다. 실수나 문자열 등에는 사용하기 어렵습니다.