도수 정렬1 카운팅 정렬 카운팅 정렬은 도수 정렬, 계수 정렬 등 다양한 이름으로 불리우는 방식입니다. 책마다, 사람마다 다른 이름을 사용하고 있지만 모두 같은 정렬을 말하고 있으며 이 블로그에서는 카운팅 정렬이라고 부를 예정입니다. 1. 카운팅 정렬 카운팅 정렬은 정렬 시 대소 관계를 판단하지 않고 정렬하는 정렬법입니다. 카운팅 정렬을 시간복잡도가 O(n)으로 빠른 알고리즘이지만, 정렬하려는 대상에 따라서 시간 복잡도가 매우 커질 수 있습니다. 정확히는 시간 복잡도가 O(n+k)이기 때문입니다. 여기서 k는 컬렉션 내부의 최대 숫자입니다. 그래서 k가 무지막지하게 커질 경우 시간도 오래걸리게 됩니다. 이렇게 되는 이유는 잠시 후 카운팅 정렬의 방식을 공부해보면 알 수 있습니다. 그리고 그동안 배운 몇 가지의 정렬법이 모두 두 .. 2021. 11. 6. 이전 1 다음 300x250
