[정렬] 계수 정렬 (카운팅 소트, Counting Sort)

계수 정렬(Counting Sort)이란 원소끼리 비교를 하지 않고 원소가 몇번 등장하는지 갯수를 세서 정렬하는 방법이다. 따라서 비교정렬이 아니고 같은 원소의 순서가 바뀌지 않는 안정정렬(stable sort)이다. 시간복잡도는 O(n + k)으로 퀵정렬, 병합정렬에 비해 일반적으로 빠르다. k: 정렬할 수들 중 가장 큰 값 n: 정렬할 수의 개수 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다. 가장 큰 숫자에 영향을 받는다는 단점이 있다. 만약 정렬해야하는 리스트가 [0, 1, 9999]일때는 배열에 2부터 9998까지 불필요한 공간을 만들어야하기 때문에 비효율적이다. 또, n의 값이 너무 커지면 일반 정렬 알고리즘보다 느려질 수 있으므로 적..
이론공부 2020. 9. 6. 23:24
1