계수 정렬(Counting Sort)은 정수나 정수 형태의 자료에 대해 선형 시간 복잡도를 가지는 안정적인 정렬 알고리즘입니다. 기존의 비교 기반 정렬 알고리즘과는 달리 계수 정렬은 비교를 사용하지 않고, 정수의 개수를 세는 방식으로 동작합니다.
이를 통해 정렬할 자료에 대한 추가 정보를 이용하여 정렬을 수행하므로, 일반적인 경우에 매우 효율적입니다. 계수 정렬의 동작 방식은 다음과 같습니다. 1.
정렬할 정수 배열에서 최솟값과 최댓값을 찾습니다. 이를 통해 배열의 범위를 파악합니다. 2.
범위 내에서 각 정수의 등장 횟수를 세어 빈도수 배열(Count 배열)에 저장합니다. Count 배열의 인덱스는 정수 값이고, 해당 인덱스의 값은 해당 정수의 등장 횟수입니다. 3.
Count 배열을 누적합으로 변환합.....
