최씨네 블로그

Counting Sort 계수 정렬은 말 그대로 데이터를 counting 하여 정렬되는 것과 마찬가지인 효과를 나타내는 정렬입니다. 앞서 보았던 정렬방식은 시간복잡도 O(N*N) 또는 O(N*logN)을 가졌습니다. 하지만 계수 정렬은 데이터를 한번씩만 접근하여 O(N)의 시간복잡도를 가질 수 있습니다. 어떻게 O(N)의 시간 복잡도를 가질 수 있을까요? 이유는 다른 정렬들은 데이터를 비교하고 위치를 바꾸지만 계수정렬은 데이터를 순차적으로 읽으면서 해당 데이터의 개수를 counting 하여 나중에 한번에 나타내는 방식이기 때문인데요. 이와 같은 이유 때문에 언제나 사용하기보다는 특정한 범위가 있고 중복이 많을 시 정렬이 효과적이라고 볼 수 있습니다. 계수정렬의 작동과정을 보면 다음과 같은 상황에 효과적입..