계수 정렬 (counting sort) : 특정 숫자의 빈도를 센다.
2가지 정렬을 배웠습니다. insert, select. 이 두 개는 키 값들을 비교를 했습니다. 2개의 값을 compare 했습니다. 제가 오늘 설명하는 counting sort, 계수 정렬은 이 둘과 크게 다른 점이 있는데요. 두 개의 키 값을 비교하지 않는다는 것입니다. 즉, 비교 기반 정렬이 아닙니다. 그러면 어떻게 구현을 할까요? arr = [3, 6, 3, 0, 4, 1]이라고 해 봅시다. 최솟값이 양수고, 최댓값 또한 적당히 작은 수라고 해 봅시다. co[x]를, 배열에서 x가 나타난 빈도수라고 정의합시다. 그러면, arr을 순회하면서, 어떠한 값 v가 나오면 co[v]의 값을 하나씩 증가시키면 될 거에요. 먼저 co 배열은 아래와 같이 초기화가 되어 있습니다. 1번째 원소를 봅니다. 3입니다..
자료알고/알고리즘
2019. 7. 20. 01:22
최근댓글