yoo.dev

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

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 그동안 수 정렬하기 문제가 있을때는 간편하게 파이썬의 sorted()를 사용했지만, 이 문제는 메모리 제한이 있어서 카운팅 소트를 사용해서 풀어야 한다. 카운팅소트(Counting Sort)란 https://yuuj.tistory.com/106 [정렬] 계수 정렬 (카운팅소트, Counting Sort) 계수 정렬(Counting Sort)이란 원소끼리 비교를 하지 않고 원소가 몇번 등장하는지 갯수를 세서 정렬하는 방법이다. 시간복잡도는 O(n + k)으로 퀵정렬, 병합..