[알고리즘] 계수 정렬 (Counting Sort), O(N)

정렬 알고리즘은 일반적으로 비교 정렬을 하는데, 각 원소의 값을 비교하지 않고 정렬하여 시간복잡도를 O(N)으로 줄이는 특수한 정렬 알고리즘이 존재한다. 그 중 하나가 계수 정렬 (Counting Sort)이다. 추가로 정렬을 하기 위해서 각 원소의 값을 최소 1번씩은 확인해야 하므로 정렬 알고리즘이 O(N)보다 시간 복잡도는 낮아질 수 없다는 것은 자명하다.  Counting Sort는 정렬하고자 하는 값의 범위가 O(N)을 넘지 않는 경우 사용할 수 있다. 예를 들어 k 이하의 자연수가 될 수 있고, 실수라고 한다면 수의 범위가 무한해지기 때문에 사용할 수 없다. Counting Sort의 동작 원리는 말 그대로 값을 세서 개수를 기록해둔 뒤 나중에 순서대로 데이터를 배치하는 것이다. 도식을 통해 이..

2024.09.07