계수 정렬(Counting Sort)은 정수나 정수 형태의 자료에 대해 선형 시간 복잡도를 가지는 안정적인 정렬 알고리즘입니다. 기존의 비교 기반 정렬 알고리즘과는 달리 계수 정렬은 비교를 사용하지 않고, 정수의 개수를 세는 방식으로 동작합니다. 이를 통해 정렬할 자료에 대한 추가 정보를 이용하여 정렬을 수행하므로, 일반적인 경우에 매우 효율적입니다.
계수 정렬의 동작 방식은 다음과 같습니다.
1. 정렬할 정수 배열에서 최솟값과 최댓값을 찾습니다. 이를 통해 배열의 범위를 파악합니다.
2. 범위 내에서 각 정수의 등장 횟수를 세어 빈도수 배열(Count 배열)에 저장합니다. Count 배열의 인덱스는 정수 값이고, 해당 인덱스의 값은 해당 정수의 등장 횟수입니다.
3. Count 배열을 누적합으로 변환합니다. 이를 통해 Count 배열의 각 인덱스에는 해당 값 이하인 정수의 개수가 저장됩니다.
4. 원래 배열을 순회하면서, 각 정수를 해당하는 Count 배열의 인덱스로 사용하여 정렬된 위치에 배치합니다. 동일한 값이 여러 개일 경우에는 누적합을 이용하여 적절한 위치에 배치합니다.
5. 정렬된 결과를 새로운 배열에 복사합니다.
계수 정렬은 정수의 범위가 크지 않고 중복된 값이 상대적으로 적은 경우에 효율적으로 동작합니다. 하지만 정수의 범위가 크고 중복된 값이 많은 경우에는 메모리 사용량이 많아질 수 있습니다. 또한, 계수 정렬은 정수 형태의 자료에만 적용할 수 있으며, 부동 소수점 수나 문자열과 같은 다른 자료형에는 적용할 수 없습니다.
계수 정렬은 안정적이고 선형 시간 복잡도를 가지는 특성 때문에 정렬해야 하는 자료의 범위가 제한되어 있고 중복된 값이 적을 때 유용하게 사용될 수 있습니다.
C++로 작성된 계수 정렬의 예시 코드입니다.
이 코드는 주어진 정수 배열을 계수 정렬을 사용하여 정렬하고, 정렬된 결과를 출력합니다.
댓글